Skip to content

Instantly share code, notes, and snippets.

@joriki
Created April 17, 2012 18:45
Show Gist options
  • Save joriki/2408136 to your computer and use it in GitHub Desktop.
Save joriki/2408136 to your computer and use it in GitHub Desktop.
Count the number of words over an alphabet of n letters without non-overlapping repeated strings of length 2
import java.util.Set;
import java.util.HashSet;
public class Question132847 {
static int n;
static int count;
static Set<String> pairs = new HashSet<String> ();
public static void main (String [] args) {
for (n = 1;n < 5;n++) {
count = 0;
recurse (' ',"");
System.out.println (n + " : " + count);
}
}
static void recurse (char last,String nextPair) {
count++;
for (int k = 0;k < n;k++) {
char next = (char) ('a' + k);
String pair = last + "" + next;
if (!pairs.contains (pair)) {
boolean added = pairs.add (nextPair);
recurse (next,pair);
if (added)
pairs.remove (nextPair);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment