# Follow up --> BinarySearch with concise code and explanation

• We can go through String "t" once to build the table, then use table to do binartSearch.
Use List to record the index corresponding to this character.

``````public boolean isSubsequence(String s, String t) {
if(s == null || s.length() == 0)  return true;
// build the table
List<Integer>[] table = new List[26]; // learn how to initialize
for(int i = 0; i < t.length(); i++) {
int index = t.charAt(i) - 'a';
if(table[index] == null)  table[index] = new ArrayList<Integer>();
table[index].add(i);
}

// go through s
int indexS = 0;
int indexT = 0;
while(indexS < s.length()) {
int num = s.charAt(indexS) - 'a';
if(table[num] == null)  return false;  // t doesn't contains this char
int index = binarySearch(table[num], indexT);
if(index == -1)  return false;
indexT = index + 1;
indexS++;
}
return true;
}
// get the lowest index larger than indexT
// consider list as array, search num inside the list
private int binarySearch(List<Integer> list, int indexT) {
int left = 0;
int right = list.size() - 1;
while(left + 1 < right) {
int mid = left + (right - left) / 2;
int index = list.get(mid);
if(index == indexT)  return index;
else if(index < indexT)  left = mid;
else  right = mid;
}
if(list.get(left) >= indexT)  return list.get(left);
if(list.get(right) >= indexT)  return list.get(right);
return -1;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.