程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Longest Common Prefix ——解題報告

Longest Common Prefix ——解題報告

編輯:C++入門知識

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;
    }
};


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved