Code & Func

恩，今天早上1,2节没课，闲来无事就先把今天的题刷了（你的算法分析实验呢？）今天的题目是Longest Common Prefix,恩，比那个什么最长公共子串简单多了，很容易就可以找到思路（虽然写出来的代码很难看）

大概的解题思路是：

先找出最短的字符串，假定他就是我们要的答案
遍历所有字符串，看他们是否有这个字符串
- 如果有就直接返回
- 如果没有就把子串长度减小，再进行重复操作

思路很简单，但我写的很渣（直接过，我也是很懵，我还想再敲多一下的）

先上我的代码吧：

1
string longestCommonPrefix(vector<string>& strs) {
2
    if (strs.empty()) return "";
3
    else if (strs.size() == 1) return strs[0];
4
    string ret =  strs[0];
5
    for(auto &s:strs) {
6
        if (ret.size() > s.size())
7
            ret = s;
8
    }
9
    while(ret.size() > 0) {
10
        bool is = true;
11
        for(auto &s:strs){
12
            if (s.substr(0,ret.size()) != ret) {
13
                is = false;
14
                break;
15
            }
7 collapsed lines
16
        }
17
        if (!is) ret = ret.substr(0,ret.size() - 1);
18
        else return ret;
19
    }
20
    return "";
21

22
}

恩，我是没想到它会直接过的，思路相当简单，当然思路简单一般效率就不会很高。

我的思路一开始是假定最短的串是我们要的结果，而在dicuss中别人的写法是另一种思路：

1
string longestCommonPrefix(vector<string>& strs) {
2
   string prefix = "";
3
    for(int idx=0; strs.size()>0; prefix+=strs[0][idx], idx++)
4
        for(int i=0; i<strs.size(); i++)
5
            if(idx >= strs[i].size() ||(i > 0 && strs[i][idx] != strs[i-1][idx]))
6
                return prefix;
7
    return prefix;
8
}

比我的代码简洁很多，他是先假定最长前缀是空，然后在用动态规划的思路去做的（恩，要好好研究一下动态规划），而且他这种写法就不需要判断传入的vector是不是空了。