#14. Longest Common Prefix

題目描述

寫一個函式找出字串陣列中最長的共同字首。

如果沒有任何共同字首，回傳空字串""。

限制條件

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]只由小寫字母組成。

解題思路

Intuition

共同字首的長度會落在 0到最短的字串之間。
0的話很好理解，就是整個陣列字串中的第一個字開始就不一致。
最短的字串是因為超出最短字串的長度，就算其他字串一致，也不算共同字首。

因此我們可以拿字串中的任一字串作為基準，逐一比對所有的字串，如果這個字串是最短字串，那麼答案肯定在範圍內，如果這個字串長度超過最短的字串，在比對途中也會發現，所以不用考慮這個問題。

public class Solution { 
	public string LongestCommonPrefix(string[] strs) {
        string ans = "";        
        for(int i=0;i<strs[0].Length;i++){            
            foreach(string str in strs){
              if(str.Length<=i) return ans;
              if(str[i]!=strs[0][i]) return ans;                
            }
            ans+=strs[0][i];
        }
        return ans;
    }
}

複雜度分析：

時間複雜度：由於要檢查所有陣列元素，因此至少為strs.Length，而元素的檢查範圍會是共同字首的範圍，因此至少會占用到陣列中所有字串的最小長度，因此時間複雜度為O(m*n)。
空間複雜度：需要一個紀錄共同字首的變數，占用的空間最多會是陣列中所有字串的最小長度，因此空間複雜度為O(n)。

學習重點

字串