3ms Java DFS


  • 0
    L
        public int minMutation(String start, String end, String[] bank) {
    
            int ans;
            boolean[] used=new boolean[bank.length+1];
            int[][] diff=new int[bank.length+1][bank.length+1];//预处理,获得任意两个字符串之间的相同位置不同字符的数量
            List<String> bankList=new ArrayList<>();
    
            bankList.add(start);
            for(String item:bank){
                if(!item.equals(start))
                    bankList.add(item);
            }
    
            for(int i=0;i<bankList.size();i++){
                for(int j=i+1;j<bankList.size();j++){
                    diff[i][j]=diffCnt(bankList.get(i),bankList.get(j));
                }
            }
    
            used[0]=true;
            ans=dfs(start,end,bankList.toArray(new String[]{}),0,diff,used,0,Integer.MAX_VALUE);
            return ans;
        }
    
        public int dfs(String cur,String end,String[] bank,int curIndex,int[][] diff,boolean[] used,int path,int min){
            boolean hasResult=false;
            int result;
            if(cur.equals(end))
                return path;
            for(int i=0;i<bank.length;i++){
                if(!used[i]&&(diff[curIndex][i]==1||diff[i][curIndex]==1)){
                    used[i]=true;
                    result= recursive(bank[i],end,bank,i,diff,used,path+1,min);
                    if(result==-1) {
                        used[i]=false;
                        continue;
                    }else{
                        hasResult=true;
                        min=Math.min(min,result);
                        used[i]=false;
                    }
                }
            }
            return hasResult?min:-1;
        }
    
        public int diffCnt(String s1,String s2){
            int count=0;
            for(int i=0;i<s1.length();i++){
                if(s2.charAt(i)!=s1.charAt(i)){
                    count++;
                }
            }
            return count;
        }
    

Log in to reply
 

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