14. Longest Common Prefix
1.問題

2.想法
提問
function header, parameter
test input
說明想法
用vector<int> 儲存每個string各字母出現的次數, 當相同字母的出現次數與字串數量相同時, increment + 1
測試計算複雜度: O(n)
3.程式碼
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int size = strs.size();
if (size == 0) {
return "";
}
vector<char> v(128, 0);
string s = "";
int maxNum = INT_MAX;
for (int i = 0; i < size; i++) {
maxNum = min(maxNum, int(strs[i].size()));
}
for (int j = 0; j < maxNum; j++) {
for (int i = 0; i < size; i++) {
v[int(strs[i][j] - '0')]++;
}
if (v[int(strs[0][j] - '0')] == size) {
s.push_back(strs[0][j]);
v[int(strs[0][j] - '0')] = 0;
} else {
return s;
}
}
return s;
}
};
Last updated