Java code for the follow-up question


  • 22
    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);
    }

  • 4

    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! :-)


  • 0
    B

    @YaokaiYang said in Java code for the follow-up question:

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

    Great explanation. Thanks for sharing the binary search solution


  • 1
    Z

    So what is the time complexity of this solution?
    For the worst case, t should be like "aaa....aaa" with the length N, the binary search is O(logN), suppose the average length of the incoming strings is M, and the number of incoming strings is K, the total runtime would be O(MKlogN).
    Am I right?


  • 0
    Y

    @zhangruoxi Yes. I think that's the runtime complexity, considering we are doing a binary search for every character in the incoming strings.


Log in to reply
 

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