LeetCode 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

分析

这个题目直接扫一遍就行了，复杂度是O(min(strlen))，strlen是字符串的长度

代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0)
            return "";
        else if(strs.size() == 1)
            return strs[0];
        int currPos = 0;
        bool shouldStop = false;
        while(!shouldStop){
            char c;
            for(int row=0; row < strs.size(); row++){
                if(strs[row].size() == currPos){
                    shouldStop = true;//Meet the end of some string
                    break;
                }
                if(row == 0){
                    c = strs[row][currPos];
                } else {
                    if(strs[row][currPos] != c){
                        shouldStop = true;
                        break;
                    }
                }
            }
            if(!shouldStop)
                currPos++;
        }
        return strs[0].substr(0, currPos);
    }
};