why memorized dfs search just beat 14% ?????? confused


  • 0
    K

    Hi,everybody,i am a rookie in programming , when i saw the method in word break II ,i learned the method of
    memorized search , so i try to use it in this problem, but the efficiency is quite not good, i wander why it's like this,
    thanks a lot. ^^

    Map<String,List<List< String> > > map= new HashMap<>();
    
        public List<List<String>> partition(String s) {
            List<List<String>> res = new ArrayList<List<String>>();
            if(s==null || s.equals("")) {
                return res;
            }
            return dfs(s,map);
        }
    
        public List<List<String>> dfs(String s, Map<String,List< List<String>>> map){
            if(map.containsKey(s) ){
                return map.get(s);
            }
            List<List<String> > res = new ArrayList<List<String>>();
            LinkedList<String> list= new LinkedList();
            if(s.equals( "") ){
                list.add("");
                res.add(list);
                map.put(s,res);
                return res;
            }
            for(int i =1;i<=s.length();i++){
                String pres= s.substring(0,i);
                if(isPalin(pres ) ){
                    List<List<String>> prelist= dfs(s.substring(i),map );
                    for(List<String> ll : prelist){
                        LinkedList<String> myl= new LinkedList<>(ll);
                        if(myl.getFirst().equals("") ){
                            myl.removeFirst();
                        }
                        myl.addFirst(pres);
                        res.add(myl);
                    }
                }
            }
            map.put(s,res);
            return res;
        }
    
        public boolean isPalin(String s){
            int len =s.length();
            int i=0,j=len-1;
            while(i<=j){
                if(s.charAt(i)!=s.charAt(j) ){
                    return false;
                }
                i++;j--;
            }
            return true;
        }
    

Log in to reply
 

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