Coupon Dunia Interview Question
SDE1sCountry: India
The answer is the number of letters in start word which are different from the letters in the finish word.
Java code:
public class StartFinish {
private static String start = "cat";
private static String finish = "hat";
public static void main(String[] args) {
System.out.println(findMinimumSteps(start, finish));
}
public static int findMinimumSteps(String start, String finish) {
int j = 0;
int cnt = 0;
for(int i = 0; i < start.length(); i++) {
if(start.charAt(i) != finish.charAt(j)) {
cnt++;
}
j++;
}
return cnt;
}
}
The problem in your approach is that.if I want to reach cat to dog it's not always a 3 step process.. What if this is the path followed
cat -> bat -> bot -> dot -> dog. So, it takes 4 steps but your answer will be 3.
I think there is no need of graph or tree. The question is asking minimum no of steps which is in worst case will be 3(three letter words: three bits to flip). Simple loop should work.
Suggestion and corrections welcomed :)
public class ChangeWord {
public static void main(String[] args) {
// TODO Auto-generated method stub
// cat -> dog : dat -> dot -> dog;
int steps = findMinimumStepsToChange("cat", "dog");
System.out.println(steps);
// pic -> cat : pic -> cic -> cac -> cat
int steps2 = findMinimumStepsToChange("pic", "cat");
System.out.println(steps2);
}
public static int findMinimumStepsToChange(String word1, String word2){
if("".equals(word1)||"".equals(word2))
return -1;
if(word1.equals(word2))return 0;
int steps = 0;
int charCount = 0;
for(int i=0;i<word1.length();i++){
if(word1.charAt(i) != word2.charAt(i)){
steps++;
}
}
return steps;
}
}
The approach is to build a graph with vertices as words. An edge exists between two vertices if the two words differ by only one character. Once the graph is constructed, you need to a BFS to obtain the path/count the number of nodes between two words.
To construct the graph, we pass the dictionary as a Set<String>
In the above code, the function oneCharDiff returns true if there is exactly one character difference between two words.
The following code navigates to the path using the above function,
Word is a simple class with 2 members - String original and String parent. This is used to print the order of the path followed.
- arsragavan March 16, 2015Time complexity : O(n^2) when constructing the graph. Any suggestions to improve the solution are welcome. There is another way to handle this problem using the backtracking method but i'm sure the complexity would be exponential in that case.