Leetcode 392: Is Subsequence

问题描述:

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));
        }
    }
}
上一篇:C#根据身份证获取身份证信息以及(一级)身份证各省级*的代码


下一篇:将一个字符串中指定位置进行反转