Back-Tracking+DFS+DP using Java


  • 0
    T
    class Solution {
        public int minStickers(String[] stickers, String target) {
             int N = target.length();
             Integer[] dp = new Integer[1<<N];
             
             return searchHelper(stickers,dp,target,0);
        }
        
        public int searchHelper(String[] stickers,Integer[] dp,String target,int state){
            if(dp[state]!=null){
                return dp[state];
            }
            
            int N=target.length();
            if(state==((1<<N)-1)){
                return 0;
            }
            
            int minCount= Integer.MAX_VALUE;
            int originalstate = state;
            for(String str:stickers){
                char[] array = str.toCharArray();
                
                for(char c:array){
                    for(int i=0;i<target.length();i++){
                        if(c==target.charAt(i) && ((state>>(target.length()-1-i))&1)==0){
                            state |= 1<<(target.length()-1-i); 
                            break;
                        }
                    }
                }
                if(state!=originalstate){
                    int count = searchHelper(stickers,dp,target,state);
                    if(count!=-1){
                       minCount = Math.min(minCount,1+count); 
                    }
                }
                
                state = originalstate;
            }
            
            if(minCount!=Integer.MAX_VALUE){
                dp[state]=minCount;
                return dp[state];
            }
            dp[state]=-1;
            return -1;
        }
    }
    
    

Log in to reply
 

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