Met a problem when using use HashMap and Binary search. Could someone please help me?


  • 0
    P

    I want to use HashMap and Binary search to solve the follow-up question, but when input is
    "acb"
    "ahbgdc"
    My output is always true which should be false. I double check my code but find nothing.
    In my code, I think it should return false because 'b' in "acb" will let {start==5==list.size} and cause {prev==-1} which will return [false]. How dose [true] come out?

    Could anyone please spend little time help me on this? Thanks!!
    My code is as follows:

    public class Solution {//follow up timeO(k*logn)
        public boolean isSubsequence(String s, String t) {
            if(s==null||t==null) return false;
            // put characters in t in a map
            Map<Character,List<Integer>> pos=new HashMap<>();
           
            int p=0;
            for(char tt : t.toCharArray()){
                if(pos.get(tt)==null){
                    pos.put(tt,new ArrayList<Integer>());
                }
                pos.get(tt).add(p++);
            }
            //check s is in pos or not
            int prev=-1;//used to check whether it exists, if not return false
            for(char ss : s.toCharArray()){
                if(pos.get(ss)==null){
                    return false;
                }else{
                
                List<Integer> list=pos.get(ss);
                prev=binarySearch(prev,list,0,list.size()-1);
                if(prev==-1){
                    return false;
                }
                
                }
            }
            return true;
        }
        
        public 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){
                    end=mid-1;
                }else{
                    start=mid+1;
                }
            }
            return start==list.size()?-1:start;
        }
        
    }
    

Log in to reply
 

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