題目:
給定字符串 s 和 t 撵彻,判斷 s 是否為 t 的子序列袱蜡。
字符串的一個子序列是原始字符串刪除一些(也可以不刪除)字符而不改變剩余字符相對位置形成的新字符串陈莽。(例如底挫,"ace"是"abcde"的一個子序列,而"aec"不是)淑际。
示例 1:
輸入:s = "abc", t = "ahbgdc"
輸出:true
示例 2:
輸入:s = "axc", t = "ahbgdc"
輸出:false
思路一:
遍歷s畏纲,假設字符為c1,t中如果不存在c1直接返回false春缕。如果存在t截取c1在t中所在位置的后半段盗胀。
代碼如下:
public boolean isSubsequence(String s, String t) {
for (int i = 0; i < s.length(); i++) {
char c1 = s.charAt(i);
if (t.indexOf(c1) == -1)
return false;
t = t.substring(t.indexOf(c1) + 1);
}
return true;
}
思路二:
雙指針,申明i為s指針锄贼,j為t的指針票灰。
當i<s.length 和 j<t.length時,如果s.charAt(i)==t.charAt(j)宅荤,說明t中存在s當前字符米间。不管有無j++,j繼續(xù)向后尋找膘侮。
當i==s.length時,說明找到了最后的榛,返回true
代碼如下:
public boolean isSubsequence1(String s, String t) {
int i = 0, j = 0;
int n = s.length(), m = t.length();
while (i < n && j < m) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == n;
}
-------------------------------小白學算法