Accepted Java recursive code


  • 0
    U
    int min = -1;
    int deep = 0;
    public int minMutation(String start, String end, String[] bank) {
        if (bank == null || bank.length == 0) {
            return -1;
        }
        
        Set<String> bankset = new HashSet<>();
        for (String s : bank) {
            bankset.add(s);
        }
        
        if (!bankset.contains(end)) {
            return -1;
        }
        
        mutation(start, end, bankset);
        return min;
    }
    
    private void mutation(String start, String end, Set<String> bank) {
        if (canChange(start, end)) {
            if (min < 0 || min > deep) {
                min = deep + 1;
            }
            return;
        }
        
        for (Object obj : bank.toArray()) {
            String mid = (String)obj;
            if (canChange(start, mid)) {
                bank.remove(mid);
                deep++;
                mutation(mid, end, bank);
                deep--;
                bank.add(mid);
            }
        }
    }
    
    private boolean canChange(String s1, String s2) {
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
        }
        if (diff == 1) {
            return true;
        } else {
            return false;
        }
    }

Log in to reply
 

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