[leetcode] [KMP] KMP

ABCDABD...

ABCDABF...

簡單的說, 傳統解兩字串匹配部分

可能會來個雙迴圈, 哀個比對, 當不匹配的時候, 會將下方列再後移1位

然後不匹配再後移

然而

如果像上放已經有4個屬於匹配的字串, 她就應該直接往後移四位來匹配, 而不是只移動1位

隱藏的思維是, 當已知匹配的, 就已知完全不能匹配的部分, 而這部分應該合理的跳過

而當它既是前墜又是後墜的時候, 可能前面就都相同可以跳過

直接開始比開始不同的地方

後贅數組定義, 是整個kmp算法根基

dp[i]: the max length k s.t. s[0:k-1] = s[i-k+1:i]

[x x x] x [x x i]

中心思想, 是得到一個next數組 類似[-1, -1, 0, 1]

當該數位置對應的數字找不到匹配時, 可往前跳向下標位置再進行比對

(網路上有不同解法有跳往下標, 或是前一個下標, 會反應在j的初始值-1或是0)

public static boolean repeatedSubstringPattern(String s) {

    if(s.equals(""))return false;

    int len = s.length();
    int[] temp = new int[len];
    int[] next=getNext(temp,s, len);
    // 比對表最後一欄位置不為-1 且 長度能被最大重複組除盡
    if (next[len-1] != -1 && len % (len - (next[len-1]+1)) == 0) {
        return true;
    }

    return false;
}

public static int[] getNext(int[]next, String s, int len){
    // 1 初始化賦予-1值
    next[0] = -1;
    int j = -1;
    char[] chars = s.toCharArray();

    for(int i = 1; i<len; i++){
        // 2 前後綴不相等時, 往前跳到指定位置再進行下迴圈(比對)
        while(j>=0&&chars[i]!=chars[j+1]){
            j = next[j];
        }
        // 3 前後綴相等, j++, 並將值放到next表中
        if(chars[i]==chars[j+1]){
            j++;
        }
        next[i]=j;
    }
    return next;
}

參考: https://www.youtube.com/watch?v=t6xa2p6fFS8&t=918s

[leetcode] [eazy] Q1002

public class Q1002 {
    public static void main(String[] args) {
        String[] words = {"bella","label","roller"};
        commonChars(words);
    }
    public static List<String> commonChars(String[] words) {
        List<String>ans = new ArrayList<>();
        int[] count = new int[26];
        Arrays.fill(count, Integer.MAX_VALUE);
        for(String str: words){
            int []cnt = new int[26];
            str.chars().forEach(c->++cnt[c-'a']);
            for(int i= 0; i<26; i++){
                count[i] = Math.min(cnt[i], count[i]);
            }
        }
        for(char c='a'; c<='z';c++){
            while(count[c-'a']-->0){
                ans.add("" + c);
            }
        }
        return ans;
    }
}

1 Arrays.fill方法沒用過, 可以用來產生空陣列

2 統計文出現次數可以用int[]count = new int[26]]

3 str.chars().forEach(c->++cnt[c-'a'])

可以用來把cnt陣列中出現的文母次數做一個統計

4 for(char c=='a';c<='z';c++){

while(count[c-'a']-->0){

ans.add(""+c);

}

}

能將陣列中出現的字母, 在轉換放進List答案中

eazy這麼難...