问题描述:
Given two strings s and t, check if s is a subsequence of t.
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).
思路:
用递归。如果s的末尾与t的末尾相同,则去掉两个末尾再比较(递归式);如果s的末尾与t的末尾不相同,则保持s不变,t去掉末尾再比较(递归式)。
直到:(1)s比t长,必定是false (2)s为空但t为空或更长,必定返回true
代码如下:
class Solution {
public boolean isSubsequence(String s, String t) {
int length_s = s.length();
int length_t = t.length();
if(length_s>length_t) return false;
if ((length_s==0)&&(length_t>=0)) return true;
int i=length_s-1;
int j=length_t-1;
if(s.charAt(i)==t.charAt(j)){
return isSubsequence(s.substring(0,i), t.substring(0,j));
}
else{
return isSubsequence(s, t.substring(0,j));
}
}
}