Java code for the follow-up question


  • 19
    Y
    /**
     * Follow-up
     * If we check each sk in this way, then it would be O(kn) time where k is the number of s and t is the length of t. 
     * This is inefficient. 
     * Since there is a lot of s, it would be reasonable to preprocess t to generate something that is easy to search for if a character of s is in t. 
     * Sounds like a HashMap, which is super suitable for search for existing stuff. 
     */
    public boolean isSubsequence(String s, String t) {
        if (s == null || t == null) return false;
        
        Map<Character, List<Integer>> map = new HashMap<>(); //<character, index>
        
        //preprocess t
        for (int i = 0; i < t.length(); i++) {
            char curr = t.charAt(i);
            if (!map.containsKey(curr)) {
                map.put(curr, new ArrayList<Integer>());
            }
            map.get(curr).add(i);
        }
        
        int prev = -1;  //index of previous character
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (map.get(c) == null)  {
                return false;
            } else {
                List<Integer> list = map.get(c);
                prev = binarySearch(prev, list, 0, list.size() - 1);
                if (prev == -1) {
                    return false;
                }
                prev++;
            }
        }
        
        return true;
    }
    
    private int binarySearch(int index, List<Integer> list, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (list.get(mid) < index) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        
        return start == list.size() ? -1 : list.get(start);
    }

  • 2

    From what I understand, your helper function binarySearch finds the first element of list that is greater than or equal to the index that is passed in. Is my understanding correct?


  • 2
    Y

    @theklam Yes. You are right. Since we always need to move forward in t regarding the index, thus we have to find out the very first character in t that is the same with the current character we are considering in s. Then we set our prev (which is the start index of substring in t) to prev++.


  • 0

    Thank you. Great solution! :-)


Log in to reply
 

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