Java Easy Solution using Recursion


  • 0
    S

    A simple code, first look which of the transformations from start to end is present in bank, if there is one found then that will be the new start and continue till we reach the end. Do let me know if you have any doubts. Thank you.

    public class Solution {
        public int minMutation(String start, String end, String[] bank) {
            if(bank == null || start == null || start.length() == 0 || end == null || end.length() == 0) {
                return 0;
            }
    
            List<String> bankStrings = new ArrayList<>();
            for(String s : bank) {
                bankStrings.add(s);
            }
    
            int count = minMutation(start, end, bank, 0, bankStrings);
            return count == 0 ? -1 : count;
        }
    
        public int minMutation(String start, String end, String[] bank, int count, List<String> bankStrings) {
            List<Integer> indices = new ArrayList<>();
            int length = start.length();
            for(int i = 0; i < length; ++i) {
                if(start.charAt(i) != end.charAt(i)) {
                    indices.add(i);
                }
            }
            int curCount = 0;
            String temp = "";
            for(int i : indices) {
                temp = start.substring(0, i) + "" + end.charAt(i) + "" + start.substring(i+1, length);
                if(bankStrings.contains(temp)) {
                    curCount = 1 + minMutation(temp, end, bank, count, bankStrings);
                }
            }
            return curCount;
        }
    }
    

  • 0
    R

    Your solution cannot pass this test case.

    "AAAAAAAA"
    "CCCCCCCC"
    ["AAAAAAAA","AAAAAAAC","AAAAAACC","AAAAACCC","AAAACCCC","AACACCCC","ACCACCCC","ACCCCCCC","CCCCCCCA"]

    You have to check if the end string is in the bank. But your method is still genuis!! Thanks!


  • 0
    D

    Very good solution and easy to understand.


  • 0
    I

    What is the time complexity for this?


  • 0
    O

    This solution fails to capture that sometimes you need to pass over a temporary sequence to go the final sequence. For instance:

    start: "AAAAAAAA"
    end: "AAAACCTT"
    bank: ["AAAAAAAA","AAAAAAAC","AAAAAACC","AAAAACCC","AAAACCCC",
    "AAAACCCT","AAAACCTT"]

    Because the code is focussing on the 'end' character, it fails to see that sometimes you need to do edits like
    AAAA -> AACC --> AATT

    where the bank would contain AAAC, AACC, AACT and AATT. The algo will try to move directly from AAAA to AAAT which is invalid. It will also try AATA, which also does not exist. If no valid 1-distance edit is in the bank (as is the case with the larger example before), the recursion does not even start. For instance, on the large example, this is being tested:

    AAAACAAA
    AAAAACAA
    AAAAAATA
    AAAAAAAT
    -1

    And now recursion happens.

    Looking at the code, and the fact that the known letter of dictionary are not used, should be a sign that this will very unlikely be a valid solution, because you need to try more options than just substring'ing current sequences. There is a clear need for generation of sequences (e.g. in this example to come up with intermediate steps), which is impossible if you don't know what the alphabet is.


Log in to reply
 

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