Q:
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
.
Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
A:
就是一个个地数,发现就行。"ace"
is a subsequence of "abcde"
while "aec"
is not).s =
"abc"
, t = "ahbgdc"
true
.s =
"axc"
, t = "ahbgdc"
false
.If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
public class Solution { public boolean isSubsequence(String s, String t) { int k =0; // index for t for(int i =0;i<s.length();i++){ char ch = s.charAt(i); while(k<t.length() && t.charAt(k) != ch){ k++; } if( k >=t.length()) return false; k++; } return true; } }
Follow up的情况,就是把 t 预先处理, save the position of each character
为了更speed up , 我们搜索的时候,把当前搜索到的位置,也保存下来。
public class Solution { public boolean isSubsequence(String s, String t) { //init : record the location for each char List<List<Integer>> all = new ArrayList<>(); for(char ch = 'a'; ch<= 'z'; ch++ ){ List<Integer> list = new ArrayList<>(); all.add(list); } for(int i =0;i<t.length(); i++){ char ch = t.charAt(i); int index = ch -'a'; all.get(index).add(i); } // now test the case for S_k int[] A = new int[26]; // all S_k starting from the first position int mostLeftIndex = -1;// before this position(inclusive), string is tested valid for(int i =0;i< s.length();i++){ char ch = s.charAt(i); List<Integer> list = all.get(ch-'a'); while( A[ch-'a'] < list.size() && list.get(A[ch-'a']) <= mostLeftIndex){ A[ch-'a'] ++; } if(A[ch-'a'] == list.size() ) return false; mostLeftIndex = list.get(A[ch-'a']); } return true; } }
No comments:
Post a Comment