Problem:
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.
思路:
先求出最短的字符长度,然后从第一个字符串的第一个字符开始,判断是不是所有字符串的对应位字符相等,然后依次比较剩下的字符。这种解法思路很简单,相应的,性能也很低。
Solution (C++):
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
int min_len = INT_MAX;
for (auto str: strs) {
if (str.size() < min_len)
min_len = str.size();
}
string pre = "";
bool flag = true;
for (int i = 0; i < min_len; ++i) {
char a = strs[0][i];
for (auto str: strs) {
if (str[i] != a) { flag = false; break; }
}
if (flag)
pre += a;
}
return pre;
}
性能:
Runtime: ms Memory Usage: MB
思路:
Solution (C++):
性能:
Runtime: ms Memory Usage: MB
原文链接: https://www.cnblogs.com/dysjtu1995/p/12570849.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/337763
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!