leetcode392. 判斷子序列

傳送門

題目： 給定字元串 s 和 t ，判斷 s 是否為 t 的子序列。

s = “abc”, t = “ahbgdc” 傳回 true.

s = “axc”, t = “ahbgdc” 傳回 false.

雙指針一起走 注意：時間是n 不是 n*m

public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        if (t.length() == 0) return false;
        int si = 0;
        for (int ti = 0; si < s.length() && ti < t.length(); si++, ti++) {
            while (ti < t.length() && t.charAt(ti) != s.charAt(si)) ti++;
            if (ti == t.length()) return false;
        }
        return si != s.length() ? false : true;
	}
           

進階：（這道題主要讨論的就是進階）

如果有大量輸入的 S，稱作S1, S2, … , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會怎樣改變代碼？ 參考

public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        if (t.length() == 0) return false;
        t = " " + t; // 這是使得s的第一個元素直接找到比對位置，不用特判
        int[][] dp = new int[t.length()][26];

        for (int j = 0; j < 26; ++j) {//注意：j是列，矩陣掃描方向是從下到上，從左到右
            int nextIndex = -1;
            for (int i = t.length() - 1; i >= 0; --i) {
                dp[i][j] = nextIndex;
                if (t.charAt(i) == (char)(j + 'a')) 
    				nextIndex = i; // 注意 再往下周遊（到上一行）這個nextIndex才有效，
                                  // 目前dp[i][j]對應的還是上一次nextIndex
            }
        }
        int i = 0;
        for (char c : s.toCharArray()) {
            i = dp[i][c - 'a'];
            if (i == -1) return false;//i=-1說明要找的不存在，
            // 注意下一次進循環才是找到上一次找的，因為t加入了”” 空格備援
            // 是以c周遊到最後一個元素的時候，進到循環之後才能判斷c在不在
        }

        return true;
    }