Tuesday, March 24, 2015

Sort String


You are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering.
*** SPOILER ALERT ***
The question was pusposefully underspecified - upon questioning it was revealed that the string O might not necessarily include all characters used in string T - the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order).

At first, I thought it is a type of counting sort, so I was trying to use an array. The spoiler reminds me that not all characters in String T is included in String O, so it probably is not. I finalized with a map implementation, which may not be the most optimal one consider the extra space I used.


public class SortString {
 public static String sortString(String T, String O){
  if(T == null || O == null || T.length() == 0 || O.length() == 0)
   return T;
  Map count = new HashMap ();
  for(int i = 0; i < O.length(); i++)
   count.put(O.charAt(i), 0);
  StringBuilder rst = new StringBuilder();
  for(int i = 0; i < T.length(); i++){
   char c = T.charAt(i);
   if(!count.containsKey(c))
    rst.append(c);
   else
    count.put(c, count.get(c) + 1);
  }
  for(int i = 0; i < O.length(); i++){
   char c = O.charAt(i);
   int num = count.get(c);
   while(num-- > 0){
    rst.append(c);
   }
  }
  return rst.toString();
 }

 public static void main(String[] args) {
  String T = "dcdavgtealgbm";
  String O = "abcdefghijkl";
  System.out.println(sortString(T, O));

 }

}

No comments:

Post a Comment