Java binary search using TreeSet got TLE


  • 3
    W

    Java binary search using TreeSet, but got TLE. For single s, it performs worse than linear 2-pointer solution for sure, but if there are many s like in the follow up, should it be better since t only got processed once?

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            int sLen = s.length(), tLen = t.length();
            if(sLen == 0) return true;
            if(sLen > tLen) return false;
            
            Map<Character, TreeSet<Integer>> map = new HashMap<>();
            for(int i = 0; i < tLen; i++) {
                char c = t.charAt(i);
                if(!map.containsKey(c)) map.put(c, new TreeSet<Integer>());
                map.get(c).add(i);
            }
            
            int lowerIndex = -1;
            for(int j = 0; j < sLen; j++) {
                char c = s.charAt(j);
                if(!map.containsKey(c)) return false;
                
                Integer index = map.get(c).higher(lowerIndex);
                if(index == null) return false;
                lowerIndex = index;
            }
            
            return true;
        }
    }
    

  • 0
    V

    I made optimizations of your code to avoid extra lookups and got MTE. Interesting that TreeSet adds this overhead, it works with ArrayList and custom "upper bound" https://leetcode.com/submissions/detail/101146582/


Log in to reply
 

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