p392

发表于 | 分类于 |

LeetCode p392 Is Subsequence 题解

1.题目：

Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).
Example 1:
s = “abc”, t = “ahbgdc”
Return true.
Example 2:
s = “axc”, t = “ahbgdc”
Return false.

题意：

输入两个字符串，判断s是否是t的子序列。

2.解题思路:

见代码，判断s字符串的每个元素是否能够被t包含。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
public class Solution {
    public boolean isSubsequence(String s, String t) {
        int ls = s.length();
		int lt = t.length();
		int i = 0, j = -1;
		int[] t26 = new int[28];
		int b = -1;
		for (; i < ls && j < lt; i++) {
			int a = s.charAt(i) - 'a';
			if (t26[a] > 0) {
				t26[a]--;
			} else {
				do {
					j++;
					if (j == lt)
						break;
					b = t.charAt(j) - 'a';
					t26[b]++;
				} while (b != a);
				if (j == lt)
					break;
				t26[b]--;
				b = -1;
			}
		}
		if (i == ls)
			return true;
		else {
			return false;
		}
    }
}

4.一些总结：