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).

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?

Credits:

Special thanks to @pbrother for adding this problem and creating all test cases.

* Method 1: 2 pointers

```Java

class Solution {

public boolean isSubsequence(String s, String t) {

int sLen = s.length(), tLen = t.length();

if(sLen > tLen) return false;

else if(sLen == 0) return true;

int index1 = 0, index2 = 0;

while(index1 < sLen && index2 < tLen){

if(s.charAt(index1) == t.charAt(index2)){

index1++;

index2++;

}else{

index2++;

}

}

return index1 == sLen;

}

}

```

* Method 2: dp

```Java

class Solution {

public boolean isSubsequence(String s, String t) {

int sLen = s.length(), tLen = t.length();

boolean[][] dp = new boolean[tLen + 1][sLen + 1];

for(int i = 0; i <= tLen; i++){

dp[i][0] = true;

}

for(int i = 1; i <= tLen; i++){

for(int j = 1; j <= sLen; j++){

if(s.charAt(j - 1) == t.charAt(i - 1)){

dp[i][j] = dp[i - 1][j - 1];

}else{

dp[i][j] |= dp[i - 1][j];

}

}

}

return dp[tLen][sLen];

}

}

```

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Note:

1. 1 <= len(bits) <= 1000.

2. bits[i] is always 0 or 1.

* Method 1: Array 7m50s

```Java

class Solution {

public boolean isOneBitCharacter(int[] bits) {

int index = 0;

while(index < bits.length){

if(index == bits.length - 1) return true;

if(bits[index] == 0) index++;

else index += 2;

}

return false;

}

}

```

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Note:

1. All words in words and S will only consists of lowercase letters.

2. The length of S will be in the range of [1, 50000].

3. The length of words will be in the range of [1, 5000].

4. The length of words[i] will be in the range of [1, 50].

* Method 1:

```Java

class Solution {

private int sLen;

private String s;

public int numMatchingSubseq(String S, String[] words) {

sLen = S.length();

s = S;

int res = 0;

for(String t : words){

if(isSub(t)) res++;

}

return res;

}

private boolean isSub(String t){

int tLen = t.length();

int index1 = 0, index2 = 0;

while(index1 < tLen && index2 < sLen){

if(s.charAt(index2) == t.charAt(index1)){

index1++;

}

index2++;

}

return index1 == tLen;

}

}

```

* Method 2: HashMap + Binary search

```Java

class Solution {

private Map<Character, List<Integer>> map;

public int numMatchingSubseq(String S, String[] words) {

this.map = new HashMap<>();

for(int i = 0; i < S.length(); i++){

char c = S.charAt(i);

List<Integer> list = map.containsKey(c) ? map.get(c): new ArrayList<>();

list.add(i);

map.put(c, list);

}

int res = 0;

for(String word : words){

if(match(word)) res++;

}

return res;

}

private boolean match(String s){

char[] arr = s.toCharArray();

int pre = -1;

for(char c : arr){

if(!map.containsKey(c)) return false;

List<Integer> list = map.get(c);

int index = Collections.binarySearch(list, pre + 1);

if(index < 0) index = -index - 1;

if(index >= list.size()) return false;

pre = list.get(index);

}

return true;

}

}

```

To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn't match x[0] = 'e'.

All these operations occur simultaneously. It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Notes:

1. 0 <= indexes.length = sources.length = targets.length <= 100

2. 0 < indexes[i] < S.length <= 1000

3. All characters in given inputs are lowercase letters.

* Method 1:

```Java

class Solution {

public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {

List<int[]> list = new ArrayList<>();

for(int i = 0; i < indexes.length; i++){

list.add(new int[]{indexes[i], i});

}

Collections.sort(list, new Comparator<int[]>(){

@Override

public int compare(int[] a, int[] b){

return b[0] - a[0];

}

});

for(int[] l : list){

if(S.substring(l[0]).startsWith(sources[l[1]])){

S = S.substring(0, l[0]) + targets[l[1]] + S.substring(l[0] + sources[l[1]].length());

}

}

return S;

}

}

```