LeetCode Note Java 00392：Is Subsequence

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 260 所需閱讀時間 ≈ 1 分鐘

判斷輸入的兩個 String s 是不是 t 的 subsequence (序列中刪除部分，但不改變剩餘序列的相對順序)。

題目

Is Subsequence Easy

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isSubsequence(String s, String t) {
        int index = 0;
        int indexa = -1;
        for (int i = 0; i < s.length(); i++) {
            char chars = s.charAt(i);
            for (int j = index; j < t.length(); j++) {
                char chart = t.charAt(j);
                if (chart == chars) {
                    indexa = j;
                    break;
                }
            }
            if (indexa < index) {
                return false;
            }
            index = indexa + 1;
        }
        return true;
    }
}

步驟：

  1. 使用 int 變數記住 String s 中每個 char 在 t 中的索引。

  2. 找過的地方不重複找，只要能依序找完，s 就是 t 的 subsequence。

重點：

  • for 迴圈使用 break 提早結束。

檢討

有人的 code 超精簡，那要腦袋很靈光才能馬上想到，目前我做不到，就能多看看。

參考資料

SIMPLE CODE || 3 LINES