backtracking method java


  • 0
    N

    brutal force backtracking method, just FYI
    158 ms

    I think the key point that to avoid TLE for backtracking is:
    You only insert the same character from hand adjacent to the board string. Think about how you play zumba in the real world, you don't need to try every character to every place in the string.

    public class Solution {
        public int findMinStep(String board, String hand) {
            StringBuilder sb=new StringBuilder(board);
            int n=hand.length();
            Map<Character,Integer> map=new HashMap<Character,Integer>();
            for(int i=0;i<n;i++) {
                if(map.containsKey(hand.charAt(i))) map.put(hand.charAt(i),map.get(hand.charAt(i))+1);
                else map.put(hand.charAt(i),1);
            }
            Set<Character> set=new HashSet<Character>();
            set.add('R');
            set.add('Y');
            set.add('B');
            set.add('G');
            set.add('W');
            int[] temp=new int[1];
            int[] solve=new int[1];
            solve[0]=100;
            dfs(map, set, sb, temp, solve);
            if(solve[0]==100) return -1;
            return solve[0];
        }
        
        private void simplify(StringBuilder sb) {
            int i=0;
            while(i<=sb.length()-3) {
                if(sb.charAt(i)==sb.charAt(i+1)&&sb.charAt(i)==sb.charAt(i+2)) {
                    int j=3;
                    while(i+j<sb.length()&&sb.charAt(i)==sb.charAt(i+j)) j++;
                    sb.delete(i, i+j);
                    i=0;
                }
                else i++;
            }
            return;
        }
        
        private void dfs(Map<Character,Integer> map, Set<Character> set, StringBuilder sb, int[] temp, int[] solve) {
            int m=sb.length();
            if(m==0) {
                solve[0]=Math.min(solve[0], temp[0]);
                return;
            }
            if(map.size()==0) return;
            for(Character c: set) {
                if(map.containsKey(c)) {
                    for(int i=0;i<m;i++) {
                        if(sb.charAt(i)==c) {
                            if(map.get(c)==1) map.remove(c);
                            else map.put(c,map.get(c)-1);
                            temp[0]++;
                            sb.insert(i,c);
                            StringBuilder front=new StringBuilder(sb);
                            simplify(front);
                            dfs(map, set, front, temp, solve);
                            temp[0]--;
                            sb.deleteCharAt(i);
                            if(map.containsKey(c)) map.put(c,map.get(c)+1);
                            else map.put(c,1);
                        }
                    }
                }
            }
            return;
        }
    }
    

Log in to reply
 

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