牛客網算法題「All-in-All」：判斷字符串子序列的 Java 實現

牛客網算法題「All-in-All」：判斷字符串子序列的 Java 實現

題目描述

給定兩個字符串 s 和 t，如果從 s 中刪除若干字符（也可以不刪除），剩餘字符按原順序連接起來恰好得到 t，則稱 t 是 s 的子序列。請編寫程序判斷 t 是否為 s 的子序列。

• 輸入：多組數據，每行兩個由數字和字母組成的字符串 s 和 t，長度 < 100,000。
• 輸出：對應每組輸出 "Yes" 或 "No"。

示例

輸入:
ABC ABC
ABC AB
ABC DE

輸出:
Yes
Yes
No

核心思路：雙指針線性掃描

這是一個經典的雙指針問題。由於只需保證字符順序一致，不要求連續，我們可以同時遍歷兩個字符串：

1. 指針 i 遍歷源字符串 s，指針 j 遍歷目標字符串 t。
2. 若 s.charAt(i) == t.charAt(j)，說明找到一個匹配字符，j++ 移動到 t 的下一個字符。
3. 無論是否匹配，i++ 繼續掃描 s。
4. 循環結束後，若 j == t.length()，說明 t 所有字符都在 s 中按序找到，輸出 "Yes"，否則 "No"。

時間複雜度 O(|s| + |t|)，空間複雜度 O(1)，完美應對 10 萬長度限制。

正確 Java 實現

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String s = scanner.next();
            String t = scanner.next();
            System.out.println(isSubsequence(s, t) ? "Yes" : "No");
        }
        scanner.close();
    }

    public static boolean isSubsequence(String source, String target) {
        int i = 0, j = 0;
        int lenS = source.length(), lenT = target.length();
        
        while (i < lenS && j < lenT) {
            if (source.charAt(i) == target.charAt(j)) {
                j++; // 目標字符匹配成功，推進目標指針
            }
            i++; // 源指針始終推進
        }
        return j == lenT; // 目標是否完全匹配
    }
}

常見錯誤理解：子串 vs 子序列

作者最初誤將題目理解為「t 必須作為連續子串出現在 s 中」（即 indexOf 判斷）。

• 子串："ABCD" 包含 "AB" (Yes)，但不包含 "AD" (No)。
• 子序列："ABCD" 同時包含 "AB" 和 "AD" (均 Yes)，因為 A 在 D 之前即可。

題目明確要求「刪除一些字符後剩餘連接」，即子序列定義，而非子串。

複雜度分析與優化建議

• 時間：O(N) 單次掃描，極其高效。
• 空間：O(1) 僅使用常數額外變量。
• 優化：若需多次查詢同一 s 的不同 t，可預處理 s 建立字符位置索引（List[256]），每次查詢用二分查找 O(|t| log |s|)。