Created
May 1, 2017 16:54
-
-
Save muatik/06b1c9eddf8b49eeefe7e6700f934f96 to your computer and use it in GitHub Desktop.
ShortestSequence
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Created by mustafaatik on 01/05/2017. | |
*/ | |
public class ShortestSequence { | |
public static void main(String[] args) { | |
turnTo("dcabe", "abcde"); | |
turnTo("abcdefghjk", "kjhgfedcba"); | |
turnTo("abcdefghjkm", "mkjhgfedcba"); | |
// EXPECTED OUTPUT | |
// dcabe --> abcde: 2 changes needed | |
// abcdefghjk --> kjhgfedcba: 9 changes needed | |
// abcdefghjkm --> mkjhgfedcba: 10 changes needed | |
} | |
static int turnTo(String text1, String text2) { | |
// text1 and text2 must have the same characters, ("abc", "abm") is not expected. | |
StringBuilder s1 = new StringBuilder(text1); | |
StringBuilder s2 = new StringBuilder(text2); | |
int ops = 0; | |
int i = 0; | |
while (i < s1.length()) { | |
if (s1.charAt(i) != s2.charAt(i)) { | |
/** | |
* searching for the right position of s1[i] by traversing s2 from i+i.th char | |
*/ | |
for (int j = i + 1; j < s2.length(); j++) { | |
if (s1.charAt(i) == s2.charAt(j)) { | |
Object temp = s1.charAt(i); | |
s1.deleteCharAt(i); | |
s1.insert(j, temp); | |
ops++; | |
} | |
} | |
} | |
else | |
i++; | |
} | |
System.out.println(text1 + " --> " + text2 + ": " + ops + " changes needed"); | |
return ops; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment