Longest Common Prefix ——解題報告

Longest Common Prefix ——解題報告

【題目】

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

【分析】

公共前綴指的是所有字符串的前綴都相同。顯然，這個最長公共前綴的長度不會超過所有字符串中最短的那個。

我們先求得最短串長minLen，然後遍歷所有字符串中的前minLen是否相等。

【代碼】

運行時間：7ms

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        if(strs.empty())
            return "";
            
        int minLen = strs[0].length(); 
        for(int i = 0; i < strs.size(); i++)
        {
            minLen = minLen < strs[i].length() ? minLen : strs[i].length();
            //minLen = min(minLen, strs[i].size());  // obtain the minimal length
        }
        
        string res = "";
        bool same = true;
        for(int j = 0; same && j < minLen; j++)
        {
            for(int k = 1; k < strs.size(); k++)
            {
                if(strs[k][j] != strs[0][j])
                {
                    same = false;
                    break;
                }
            }
            if(same)
                res = res + strs[0][j];  // after the loop, res should ++
        }
        return res;
    }
};