Skip to content

Instantly share code, notes, and snippets.

@tonygwu

tonygwu/Palindrome.java

Created December 5, 2014 06:29
Show Gist options
  • Save tonygwu/6e247d2c15bcb3d30bf9 to your computer and use it in GitHub Desktop.
Save tonygwu/6e247d2c15bcb3d30bf9 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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;
}
}
Raw
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"));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment