Suppose
there are two strings str1, str2. Convert str2 to str1 by using following
operation. Put any character from str2 and insert it at front.
Ex: str1 =
"acdb" str2 = "abcd"
"abcd"
is converted to "dabc"
"dabc"
is converted to "cdab"
"cdab"
is converted to "acdb"
import java.util.Arrays; import java.util.Objects; public class StringTransform { private static boolean isTraformationPossible(String str1, String str2) { char[] chars1 = str1.toCharArray(); char[] chars2 = str2.toCharArray(); Arrays.sort(chars1); Arrays.sort(chars2); String sorted1 = new String(chars1); String sorted2 = new String(chars2); if (sorted1.equals(sorted2)) return true; return false; } private static String removeChartAt(String str, int index) { return str.substring(0, index) + "" + str.substring(index + 1, str.length()); } public static void transformString(String str1, String str2) { Objects.nonNull(str1); Objects.nonNull(str2); /* First will check whether transformation is possible or not */ if (!isTraformationPossible(str1, str2)) return; int length = str1.length() - 1; while (!str1.equals(str2)) { if (str1.charAt(length) != str2.charAt(length)) { String temp = str2; str2 = str2.charAt(length) + "" + removeChartAt(str2, length); System.out.println("Pick " + temp.charAt(length) + " Insert at front," + temp + " => " + str2); continue; } length--; } System.out.println("----------------------------"); } public static void main(String args[]) { String str1 = "acdb", str2 = "abcd"; transformString(str1, str2); str1 = "EABCD"; str2 = "EACBD"; transformString(str1, str2); str1 = "ABCDEFGH"; str2 = "GFCDEABH"; transformString(str1, str2); str1 = "EABCD"; str2 = "AECBD"; transformString(str1, str2); } }
Output
Pick d Insert at front,abcd => dabc Pick c Insert at front,dabc => cdab Pick a Insert at front,cdab => acdb ---------------------------- Pick B Insert at front,EACBD => BEACD Pick A Insert at front,BEACD => ABECD Pick E Insert at front,ABECD => EABCD ---------------------------- Pick B Insert at front,GFCDEABH => BGFCDEAH Pick A Insert at front,BGFCDEAH => ABGFCDEH Pick E Insert at front,ABGFCDEH => EABGFCDH Pick D Insert at front,EABGFCDH => DEABGFCH Pick C Insert at front,DEABGFCH => CDEABGFH Pick F Insert at front,CDEABGFH => FCDEABGH Pick B Insert at front,FCDEABGH => BFCDEAGH Pick A Insert at front,BFCDEAGH => ABFCDEGH Pick E Insert at front,ABFCDEGH => EABFCDGH Pick D Insert at front,EABFCDGH => DEABFCGH Pick C Insert at front,DEABFCGH => CDEABFGH Pick B Insert at front,CDEABFGH => BCDEAFGH Pick A Insert at front,BCDEAFGH => ABCDEFGH ---------------------------- Pick B Insert at front,AECBD => BAECD Pick E Insert at front,BAECD => EBACD Pick A Insert at front,EBACD => AEBCD Pick E Insert at front,AEBCD => EABCD ----------------------------
No comments:
Post a Comment