最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串。

1.substr

解法1：暴力循环 + substr字符串截取

runtime beats 73.15 % of cpp submissions

memory usage beats 27.86 % of cpp submissions (9 MB)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";
        string ans = strs[0];
        for (int i = 1; i < strs.size(); ++i) {
            int index = 0;
            for (;index < max(strs[i].length(), ans.length()) && ans[index] == strs[i][index]; ++index);
            ans = strs[i].substr(0, index);
        }
        return ans;
    }
};

2.+=操作

解法2：暴力循环 + 字符串的+=操作（取消了对substr的引用，性能更优）

runtime beats 73.15 % of cpp submissions

memory usage beats 92.63 % of cpp submissions (8.8 MB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 0) return "";
        string ans = strs[0];
        string temp;
        for (int i = 1; i < strs.size(); ++i) {
            temp = ans;
            ans = "";//避开新字符串长度更小的问题
            for (int j = 0; j < strs[i].length() && j < temp.length(); ++j) {
                if (strs[i][j] == temp[j]) {
                    ans += temp[j];
                } else {
                    break;
                }
            }
        }
        return ans;
    }
};