每天一道LeeCode9 【 最長公共字首】

最長公共字首

編寫一個函數來查找字元串數組中的最長公共字首。

如果不存在公共字首，傳回空字元串 

""

。

示例 1:

輸入: ["flower","flow","flight"]
輸出: "fl"
      

示例 2:

輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共字首。
      

說明:

所有輸入隻包含小寫字母 

a-z

 。

思路

對每一個字元串求得最短長度，取第一個字元串的最短長度為标準，周遊标準字元串的每一位，如果後面的n-1個字元串的對應位是相同的則繼續判斷，直到n-1個字元串周遊完成或出現不同的位。如果這一位周遊完成則結果加上這一位，否正傳回原來的結果。

答案

class Solution {
public:
string longestCommonPrefix(vector<string>& strs)
{
        string res="";
        if(strs.empty())
        {
            return res;
        }
        int min_num = strs[0].size();
        for(int i=1;i<strs.size();i++)
        {
            if(min_num>strs[i].size())
            {
                min_num = strs[i].size();
            }
        }

    
        for(int i = 0;i<min_num;i++)
        {
            char stand = strs[0][i];//第一個string的前min_num位當作是标準
            for(int j = 1;j<strs.size();j++)//周遊除掉第一個的剩餘的所有字元串
            {
                if(strs[j][i]==stand)//不全是标準位
                {
                  continue;
                }
                return res;
            }
            res += stand;
        }

        return res;

    }
};
           

注：如果隻是簡單地取strs[0]的長度作為最短長度，那麼當strs[0]的長度不是最短的時，對後面比strs[0]的長度短的string按理說應該出現越界的問題，奇怪的是并沒有。。。代碼如下：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string result="";
        if(strs.empty())
            return result;
        int i=0;
        while(i<strs[0].size())
        {
            char temp=strs[0][i];
            for(int j=1;j<strs.size();j++)
            {
                if(strs[j][i]==temp)
                    continue;
                else
                    return result;
            }
            result+=temp;
            i++;               
        }
        return result;
    }
};