CTCI Chapter 1: Arrays and Strings

ArraysAndStrings.java

package Exercise;
import java.util.HashMap;


public class ArraysAndStrings {
  public static boolean isUniq(String s) {
    int len = s.length();
    boolean isUniq = true;
    for (int i = 0; isUniq && i < len; ++i) {
      char c = s.charAt(i);
      for (int j = i + 1; isUniq && j < len; ++j)
        if (s.charAt(j) == c) isUniq = false;
    } return isUniq;
  }

  public static String uniq(String s) {
    int len = s.length();
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < len; ++i) {
      String c = s.substring(i,i+1);
      boolean isUniq = true;
      for (int j = 0; isUniq && j < i; ++j) {
        String d = s.substring(j,j+1);
        if (c.charAt(0) == d.charAt(0)) isUniq = false;
      }
      if (isUniq) result.append(c);
    } return result.toString();
  }

  public static HashMap<Character,Integer> cords(String s) {
    int l = s.length();
    String u = uniq(s);
    HashMap<Character,Integer> cords = new HashMap<Character,Integer>(u.length());
    for (int i = 0; i < l; ++i) {
      Character c = s.charAt(i);
      Integer num = cords.remove(c);
      if (num == null) num = 0;
      System.out.println(Character.toString(c) + " => " + Integer.toString(i));
      cords.put(c, num + 1);
    } return cords;
  }

  public static boolean arePerms(String a, String b) {
    HashMap<Character,Integer> aCords = cords(a);
    HashMap<Character,Integer> bCords = cords(b);
    for (Character c : aCords.keySet())
      if (bCords.containsKey(c) && bCords.get(c) != aCords.get(c))
        return false;
    return true;
  }

  public static String compress(String s) {
    String u = uniq(s);
    StringBuilder result = new StringBuilder();
    HashMap<Character,Integer> cords = cords(s);
    int len = s.length();
    for (int i = 0; i < len; ++i) {
      char c = s.charAt(i);
      int j = i + 1;
      while (j < len && s.charAt(j) == c) ++j;
      result.append(Character.toString(c));
      result.append(Integer.toString(j - i));
      i += j - i - 1;
    }
    String t = result.toString();
    return t.length() >= len ? s : t;
  }
}

ArraysAndStringsTest.java

import java.util.HashMap;
import junit.framework.TestCase;
import Exercise.ArraysAndStrings;


public class ArraysAndStringsTest extends TestCase {
  HashMap<Character,Integer> cords;

  protected void setUp() {
    cords = new HashMap<Character,Integer>();
  }

  protected void tearDown() {
    cords = null;
  }

  public void testUniq1() {
    assertTrue(ArraysAndStrings.isUniq("a"));
  }

  public void testUniq2() {
    assertTrue(ArraysAndStrings.isUniq("abcdefghijklmnopqrstuvwxyz"));
  }

  public void testNotUniq1() {
    assertFalse(ArraysAndStrings.isUniq("aaabcdefg"));
  }

  public void testNotUniq2() {
    assertFalse(ArraysAndStrings.isUniq("abcdefga"));
  }

  public void testUniqOnEmpty() {
    assertEquals("", ArraysAndStrings.uniq(""));
  }

  public void testUniqOnRepeatedChar() {
    assertEquals("a", ArraysAndStrings.uniq("aaa"));
  }

  public void testUniqKeepsFirstOccurrence() {
    assertEquals("ab", ArraysAndStrings.uniq("aba"));
  }

  public void testCordsOnEmpty() {
    assertEquals(cords, ArraysAndStrings.cords(""));
  }

  public void testCordsOnRepeatedChar() {
    cords.put('a', 3);
    assertEquals(cords, ArraysAndStrings.cords("aaa"));
  }

  public void testCordsOnMultipleChars() {
    cords.put('a', 1);
    cords.put('b', 2);
    cords.put('c', 3);
    assertEquals(cords, ArraysAndStrings.cords("cabcbc"));
  }

  public void testArePermsOnEmpties() {
    assertTrue(ArraysAndStrings.arePerms("", ""));
  }

  public void testArePermsOnRepeatedChar() {
    assertFalse(ArraysAndStrings.arePerms("a", "aa"));
  }

  public void testsArePermsOnPerms() {
    assertTrue(ArraysAndStrings.arePerms("abc", "cba"));
  }

  public void testsArePermsOnNotPerms() {
    assertFalse(ArraysAndStrings.arePerms("abc", "abb"));
  }

  public void testCompressOnEmpty() {
    assertEquals("", ArraysAndStrings.compress(""));
  }

  public void testCompressOnRepeatedChar() {
    assertEquals("a3", ArraysAndStrings.compress("aaa"));
  }

  public void testCompressOnMultipleChars() {
    assertEquals("a4b2c1", ArraysAndStrings.compress("aaaabbc"));
  }

  public void testCompressOnMultipleAppearances() {
    assertEquals("a3b1a3", ArraysAndStrings.compress("aaabaaa"));
  }

  public void testCompressNotBetterForChar() {
    assertEquals("a", ArraysAndStrings.compress("a"));
  }

  public void testCompressNotBetterForString() {
    assertEquals("aabcc", ArraysAndStrings.compress("aabcc"));
  }
}