#c++ #algorithm #java

Longest Common Prefix (Leetcode 14 Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.

这道题实际上没有涉及到过多的技巧，但是深究下去其实有很多种解决办法，这篇blog先列出两种相同思路的解决办法，是最容易想到的两种。时间复杂度均为O (S), S为所有字符串的字符数总和。

1. Horizontal Scanning

解题思路原文在LeetCode中都有。这里给一个链接

我根据自己的理解对其中的图解做一个说明和给出c++代码与注释。

以下图片引用自 Leetcode

①假设选定第一个单词leets为LCP(longest common prefix),从左到右依次比较。先与leetcode对比，不断丢弃LCP(leets)的尾部字符直到成为leetcode的一个前缀，这时LCP变为leet，这是当前扫描到的前两个单词的LCP。

②用当前LCP(leet)去跟下一个单词作对比，发现两单词相同，直接跳过。

③用当前LCP(leet)跟下一个单词leeds作对比，不断抛弃leet的末尾字符直到成为leeds的一个前缀，即LCP此时为lee

④扫描完毕。扫描到的所有单词的LCP最终为lee。

下面是c++代码的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0) //如果输入为空直接返回""
            return "";
        string prefix = strs[0];//选定第一个单词为LCP
        //横向对每一个单词扫描
        for(int i=1;i<strs.size();i++) { 
            //当LCP还未变成当前单词的一个前缀,继续抛弃末尾字符
            //Java 可用 String类的indexOf方法
            while(strs[i].find(prefix, 0) != 0) { 
                //抛弃末尾字符
                prefix = prefix.substr(0,prefix.length()-1);
                //如果LCP已经抛弃到最后一个字符了还不能成为当前单词的前缀
                //直接返回空""
                if(prefix == "") {
                    return "";
                }
            }
        }
        return prefix;
    }
};

2.Vertical Scanning

横向扫描是一整个单词作单位来比较，垂直则是从第一个单词的第一个字符开始依次和接下来的单词的第一个字符做对比，如果相同则对比下一个字符，如果不相同则结束对比，寻得LCP。直接给出官方的Java代码。

1
2
3
4
5
6
7
8
9
10
11
public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int i = 0; i < strs[0].length() ; i++){
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j ++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c)
                return strs[0].substring(0, i);             
        }
    }
    return strs[0];
}

应该较好理解。

3.To be continue…

还有两种解法一种是在扫描法的基础上应用了分治的思想。还有一种是用二分的思想。

我还未仔细阅读这两种方法。等弄懂了有时间会将这两种也上传。

#c++ #algorithm #java