Wednesday, 19 August 2015

Transform one string to another

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