iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 3
5
Software Development

從LeetCode學演算法系列 第 3

[Day 3] 從LeetCode學演算法 - 0014. Longest Common Prefix (Easy)

目標:
這題主要目的在於練習常見的字串比對處理。

原題:

Question:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.

分析/解題:
題目要求從一組字串陣列中找出其最長的共用前綴,
字串只會由a到z所構成,若沒有的話則回傳空字串。

同樣的,若遇到這個問題,請第一時間記得問他們有沒有排序XD
依據資料的分布不同,不同的解法應該會有不同的優勢,
但非特殊情況的話,總體時間複雜度應為: O(單一字串長 * 總字串數)

最直觀的想法,就是從頭開始將每個相同位置的字元比對一次,
相同則往下繼續做,不同則停下將結果輸出,
但這麼做可能前面每次都要掃過相同位置的所有字元。

我們可以換個角度想,若先拿第一個字串當作common prefix(命名作pre),
接下來用其餘的字串來檢查這個pre是否是其prefix,是的話則檢查下一個,
不是的話就將pre的尾端刪去重新檢查,這樣一旦當中有一個字串有大幅度差異,
我們很快就能將pre縮減到很短。

Java:

class Solution {
    public String longestCommonPrefix(String[] strs) {        
        if (strs == null || strs.length == 0) return "";
        String pre = strs[0];
        int i = 1;
        while (i < strs.length){
            while (strs[i].indexOf(pre) != 0)
                pre = pre.substring(0, pre.length() - 1);
            i++;
        }
        return pre;
    }
}

留意這當中我們使用了String.indexOf()來檢查,
我們只想要pre在剛好0的位置,所以不論這個值是>0(表示出現在中間)
或<0(根本沒出現),都代表pre需要被調整。
實測上這個解是當前LeetCode上對test cases跑最快的版本(0 ms)。
如果是Python的話,會有比較有趣的解法。
Python支援的min()和max()可以讓我們在List[str]中列出依字母排列順序
最小和最大的字串。當我們可以很簡單拿到這個值時,
我們可以換一個思路,從頭到尾比較的時候,
我們其實只需比最小和最大的兩個字串就好,當它們是相同字元時則往下繼續,
否則就回傳至目前為止的substring。
(因為排序最大和排序最小在某個index字元相同時,
即代表著中間其他字串在此index字元亦相同)

Python:

class Solution:
    def longestCommonPrefix(self, strs: 'List[str]') -> 'str':
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        
        for i, c in enumerate(s1):
            if c != s2[i]:
                return s1[:i]
        return s1        

面試實際可能會遇到的問題:
「如果不能用indexOf的話你會怎麼做?」
(可使用String.toCharArray()轉成陣列後再操作)
「如果這組陣列被預期長短差異很大呢?」
(先掃過一遍陣列,拿最短的當pre)
「Best Case和Worst Case的時間複雜度?什麼狀況下會發生?」
(依照你的解法應該有所不同)
「如果加入<0的判斷式的話可以提升這個程式的效率嗎?」
(不一定,因為不保證多快能遇到前綴完全不同的字串,
所以端看這組資料是預期很有可能出現結果為空字串,
還是大多數都會有共同前綴來決定。)
從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0015. 3Sum (Medium)


上一篇
[Day 2] 從LeetCode學演算法 - 0001. Two Sum (Easy)
下一篇
[Day 4] 從LeetCode學演算法 - 0015. 3Sum (Medium)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言