Java binary search for the followup question


  • 0
    J
    public class Solution {
        public boolean isSubsequence(String s, String t) {
            if(s==null && t==null) return true;
            if(s==null || t==null) return false;
            if(s.equals("")) return true;
            if(s.length()>t.length()) return false;
            
            ArrayList<Integer>[] indexes = new ArrayList[26];
            for(int i=0; i<26; i++) {
                indexes[i] = new ArrayList<Integer>();
            }
            
            for(int i=0; i<t.length(); i++) {
                indexes[t.charAt(i)-'a'].add(i);
            } 
            
            int lastIndexJ = -1;
            for(int i=0; i<s.length(); i++) {
                ArrayList<Integer> indexList = indexes[s.charAt(i)-'a'];
                
                if(indexList.size()==0) { // no such character in T
                    return false;
                }
                
                int index = Collections.binarySearch(indexList, lastIndexJ+1);
                if(index<0) {
                    index = -1-index;
                }
                    
                if(index==indexList.size()) { // the insertion point is at the end of indexList, hence doesn't exist in indexList
                    return false;
                }
                
                            
                lastIndexJ = indexList.get(index);
    
            }
            
            return true;
            
        }
    }
    

Log in to reply
 

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