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

LeetCode --- 14. Longest Common Prefix

編輯:C++入門知識

LeetCode --- 14. Longest Common Prefix


 

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

這道題的要求是在字符串數組中找到最長公共前綴。

思路比較簡單,就是兩個字符串逐個比較,找最長公共子串。這裡采用將每個字符串都與第一個字符串相比較,求最長子串。

時間復雜度:O(nm)(n是字符串數組長度,m是字符串長度)

空間復雜度:O(1)

 1 class Solution
 2 {
 3 public:
 4     string longestCommonPrefix(vector &strs)
 5     {
 6         if(strs.size() == 0)
 7             return ;
 8         
 9         string pre = strs[0];
10         for(int i = 1, j; i < strs.size(); ++ i)
11         {
12             for(j = 0; j < pre.size() && j < strs[i].size(); ++ j)
13                 if(pre[j] != strs[i][j])
14                     break;
15             pre = pre.substr(0, j);
16         }
17         return pre;
18     }
19 };

 

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