Follow up --> BinarySearch with concise code and explanation


  • 0
    G

    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;
    }

Log in to reply
 

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