Palindrome.java

package com.tonygwu.puzzles.dp;

import java.util.*;

import com.tonygwu.utils.Pair;

/**
 * Given a string s, find all palindromes within it. Does not have to be contiguous.
 * @author tony
 *
 */
public class Palindrome {

	/**
	 * Computes pairs of integers for each value in string s.
	 * @param s
	 * @return
	 */
	List<Pair<Integer, Integer>> computePairs(String s) {
		final List<Pair<Integer, Integer>> pairs = new ArrayList<>();
		for (int i = 0; i < s.length(); i++) {
			for (int j = i + 1; j < s.length(); j++) {
				if (s.charAt(i) == s.charAt(j)) {
					pairs.add(Pair.of(i, j));
				}
			}
		}
		Collections.sort(pairs, new Comparator<Pair<Integer, Integer>>() {
			@Override
			public int compare(Pair<Integer, Integer> o1,
					Pair<Integer, Integer> o2) {
				return o2.first == o1.first ? o1.second - o2.second : o1.first - o2.first;
			}
		});
		return pairs;
	}
	
	List<List<Pair<Integer, Integer>>> buildNewSetOfPalindromes(List<Pair<Integer, Integer>> oldPalindrome, List<Pair<Integer, Integer>> pairs) {
		List<List<Pair<Integer, Integer>>> newPalindromes = new ArrayList<>();
		for (Pair<Integer, Integer> pair : pairs) {
			final Pair<Integer, Integer> outerMost = oldPalindrome.get(oldPalindrome.size() - 1);
			if (pair.first < outerMost.first && pair.second > outerMost.second) {
				List<Pair<Integer, Integer>> newPalindrome = new ArrayList<>(oldPalindrome);
				newPalindrome.add(pair);
				newPalindromes.add(newPalindrome);
			} else if (pair.first >= outerMost.first) {
				break;
			}
		}
		return newPalindromes;
	}

	String convertSolution(String s, List<Pair<Integer, Integer>> palindrome) {
		final StringBuilder sb = new StringBuilder();
		final StringBuilder sb2 = new StringBuilder();

		for (Pair<Integer, Integer> pair : palindrome) {
			sb.append(s.charAt(pair.first));
			if (pair.first != pair.second) {
				sb2.append(s.charAt(pair.second));
			}
		}
		sb.reverse().append(sb2);
		return sb.toString();
	}
	
	public Set<String> solve(String s) {
		final List<Pair<Integer, Integer>> pairs = computePairs(s);
		List<List<Pair<Integer, Integer>>>[] palindromes = new ArrayList[s.length()];
		palindromes[0] = new ArrayList<>();
		for (int i = 0; i < s.length(); i++) {
			List<Pair<Integer, Integer>> l = new ArrayList<>();
			l.add(Pair.of(i, i));
			palindromes[0].add(l);
		}
		palindromes[1] = new ArrayList<>();
		for (Pair<Integer, Integer> pair : pairs) {
			List<Pair<Integer, Integer>> l = new ArrayList<>();
			l.add(pair);
			palindromes[1].add(l);
		}
		for (int i = 2; i < s.length(); i++) {
			palindromes[i] = new ArrayList<>();
			for (List<Pair<Integer, Integer>> oldPalindrome : palindromes[i - 2]) {
				palindromes[i].addAll(buildNewSetOfPalindromes(oldPalindrome, pairs));
			}
		}

		Set<String> solution = new HashSet<>();
		for (List<List<Pair<Integer, Integer>>> thePalindromes : palindromes) {
			for (List<Pair<Integer, Integer>> palindrome : thePalindromes) {
				solution.add(convertSolution(s, palindrome));
			}
		}
		return solution;
	}
}

PalindromeTest.java

package com.tonygwu.puzzles.dp;

import static org.junit.Assert.*;

import java.util.*;

import org.junit.Before;
import org.junit.Test;

import com.tonygwu.utils.Pair;

public class PalindromeTest {
	
	Palindrome solution;

	@Before
	public void setUp() throws Exception {
		solution = new Palindrome();
	}

	@Test
	public final void testComputePairs() {
		final String input = "ACGATGTAC";
		final List<Pair<Integer, Integer>> expected = new ArrayList<>();
		expected.add(Pair.of(0, 3));
		expected.add(Pair.of(0, 7));
		expected.add(Pair.of(1, 8));
		expected.add(Pair.of(2, 5));
		expected.add(Pair.of(3, 7));
		expected.add(Pair.of(4, 6));
		final List<Pair<Integer, Integer>> actual = solution.computePairs(input);
		assertEquals(expected, actual);
	}
	
	@Test
	public final void testBuildNewSetOfPalindromes() {
		final List<Pair<Integer, Integer>> pairs = new ArrayList<>();
		pairs.add(Pair.of(1, 5));
		pairs.add(Pair.of(0, 6));
		
		final List<Pair<Integer, Integer>> oldPalindrome = new ArrayList<>();
		oldPalindrome.add(Pair.of(3, 3));
		oldPalindrome.add(Pair.of(2, 4));
		
		final List<List<Pair<Integer, Integer>>> expected = new ArrayList<>();
		final List<Pair<Integer, Integer>> l1 = new ArrayList<>();
		l1.add(Pair.of(3, 3));
		l1.add(Pair.of(2, 4));
		l1.add(Pair.of(1, 5));
		expected.add(l1);
		final List<Pair<Integer, Integer>> l2 = new ArrayList<>();
		l2.add(Pair.of(3, 3));
		l2.add(Pair.of(2, 4));
		l2.add(Pair.of(0, 6));
		expected.add(l2);
		
		List<List<Pair<Integer, Integer>>> actual = solution.buildNewSetOfPalindromes(oldPalindrome, pairs); 
		assertEquals(expected, actual);
	}
	
	@Test
	public final void testConvertSolution() {
		final String input = "ACGATGTAC";
		List<Pair<Integer, Integer>> palindrome = new ArrayList<>();
		palindrome.add(Pair.of(0, 7));
		palindrome.add(Pair.of(4, 6));
		
		final String expected = "ATTA";
		final String actual = solution.convertSolution(input, palindrome);
		assertEquals(expected, actual);
	}
	
	@Test
	public final void test() {
		final String input = "ACGATGTAC";
		final Set<String> expected = new HashSet<>();
		expected.add("A");
		expected.add("C");
		expected.add("G");
		expected.add("A");
		expected.add("T");
		expected.add("AA");
		expected.add("AA");
		expected.add("AA");
		expected.add("AA");
		
		final Set<String> actual = solution.solve(input);
//		assertEquals(expected, actual);
		assertTrue(actual.contains("A"));
		assertTrue(actual.contains("C"));
		assertTrue(actual.contains("G"));
		assertTrue(actual.contains("A"));
		assertTrue(actual.contains("T"));
		assertTrue(actual.contains("AA"));
		assertTrue(actual.contains("TT"));
		assertTrue(actual.contains("GG"));
		assertTrue(actual.contains("CC"));
		assertTrue(actual.contains("ATTA"));
		assertTrue(actual.contains("CATTAC"));
		assertTrue(actual.contains("ATGTA"));
		assertTrue(actual.contains("CTGTC"));
		assertTrue(actual.contains("CATAC"));
		assertTrue(actual.contains("GTG"));
	}

}