My solution using index, optimized for follow up


  • 0
    X

    I found most top viewed solutiosn here use two pointers, which scans t at least one time for each given input s. It becomes expensive when calling multiple times for one long t.

    The solution below stores characters in t into an index of positions. And for each char c in input s, it finds the smallest possible position and keep searching for the next ones until finish scanning s or no results.

    Thus we can only scan string t only once.

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            List<List<Integer>> bucket = new ArrayList<List<Integer>>(26);
            for (int i = 0; i < 26; i++) {
                bucket.add(new ArrayList<Integer>());
            }
            
            for (int i = 0; i < t.length(); i++) {
                char c = t.charAt(i);
                bucket.get(c - 'a').add(i);
            }
            
            int lastPos = -2;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                lastPos = bSearchNext(bucket.get(c - 'a'), lastPos);
                if (lastPos == -1) {
                    return false;
                }
            }
            
            return true;
        }
        
        // find the right next value bigger than target, -1 if no found. Check LC35.
        private int bSearchNext(List<Integer> nums, int target) {
            if (nums.isEmpty() || nums.get(nums.size() - 1) <= target) {
                return -1;
            }
            
            int begin = 0;
            int end = nums.size() - 1;
            while (begin <= end) {
                int mid = (begin + end) / 2;
                if (nums.get(mid) == target) {
                    return nums.get(mid + 1);
                } else if (nums.get(mid) < target) {
                    begin = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            
            return nums.get(begin);
        }
    }
    

Log in to reply
 

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