Tuesday, June 9, 2015

Leetcode: longest common prefix

First time to study the question on Aprill 29. And read the website:
纵向扫描
// LeetCode, Longest Common Prefix
// 纵向扫描,从位置0 开始,对每一个位置比较所有字符串,直到遇到一个不匹配
// 时间复杂度O(n1+n2+...)
// @author 周倩(http://weibo.com/zhouditty)
class Solution {
public:
string longestCommonPrefix(vector &strs) {
if (strs.empty()) return "";
for (int idx = 0; idx < strs[0].size(); ++idx) { // 纵向扫描
for (int i = 1; i < strs.size(); ++i) {
if (strs[i][idx] != strs[0][idx]) return strs[0].substr(0,idx);
}
}
return strs[0];
}
};

No comments:

Post a Comment