Wednesday, December 12, 2012

[leetcode] longest common prefix


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


这个简单,差不多一遍通过:)


class Solution {
public:
    string longestCommonPrefix(vector &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
     
        if (strs.empty())
        {
            return string("");
        }
     
        // first find the minimum string length
        int min_len = strs[0].length();
     
        for (int i = 0; i < strs.size(); i++)
        {
            if (min_len > strs[i].length())
                min_len = strs[i].length();
        }
     
        // compare staring at [min_len-1]
        int length = 0;
        for (int index = 0; index < min_len; index++)
        {
            bool all_equal = true;
            for (int cur = 1; cur < strs.size(); cur++)
            {
                if (strs[cur-1][index] != strs[cur][index])
                {
                    all_equal = false;
                    break;
                }
            }
            if (all_equal)
                length = index + 1;
            else
                break;
        }
     
        return strs[0].substr(0,length);
    }
};

No comments: