iT邦幫忙

DAY 25
2

連續30天,挑戰演算法系列 第 25

[Day25] 30 天挑戰演算法 - 最長的共同字首(prefix)

題目來源Longest Common Prefix

問題:
撰寫一個 功能 可以從一個 String Array 中找到最長的共同字首 (prefix)

例子
假設 輸入陣列字串 = ["Super", "Superman", "Superwoman", "Soupe"]
則最長的共同字首就是 S

想法
這個題目我們可以換句話說,也就是「給你兩個字串,要你找出共同的子字串。」這樣一來就變的相對簡單了。
我們只要先寫一個子程序,目的是要比較兩個字串並找出這兩個字串的共同字首,接著再從陣列裡把每個字串,兩兩相比,答案就出來了!

首先,先找出兩個字串中的共同字串
找出共同子字串

public String findMatchSubString(String string1, String string2) {
    int length = string1.length() >= string2.length()? string2.length():string1.length();    
    
    StringBuilder result = new StringBuilder();
    for(int index=0; index<length; index++) {
        if (string1.charAt(index)==string2.charAt(index))
            result.append(string1.charAt(index));
        else
            break;
    }
    return result.toString();
}

接著,就可以把輸入的 String Array 裡的字串拿出來,兩兩相比,最後就可以達到結果了。

public String findLongestCommonPrefix(String[] strs) {
    String result = strs[0];
    for(int index = 1; index<strs.length; index++)
        result = findMatchSubString(result);
    return result;
}

這樣就可以從輸入的字串陣列中找到最長的共同字首了,不過這樣的缺點是時間複雜度稍稍高了些,是 O(MN)


上一篇
[Day24] 30 天挑戰演算法 - 反轉文字字串
下一篇
[Day26] 30 天挑戰演算法 - 從List的尾巴刪除第N個節點
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言