Skip to content

Instantly share code, notes, and snippets.

@schmohlio
Created January 18, 2017 22:11
Show Gist options
  • Save schmohlio/15b42bcb42b1091e4a728e41a539e948 to your computer and use it in GitHub Desktop.
Save schmohlio/15b42bcb42b1091e4a728e41a539e948 to your computer and use it in GitHub Desktop.
"String Chains" brain teaser
package io.schmohl;
import java.util.*;
public class StringChain {
// we can use depth first search for each word to calculate the length of the chain.
static int longestChain(String[] words) {
// create something with O(1) searching of words.
final Set<String> wordMap = new HashSet<>();
for (String e : words) wordMap.add(e);
int max = -1;
for (String target : words) {
int k = depthFirstCount(target, wordMap);
if (k > max) max = k;
}
return max;
}
private static int depthFirstCount(String target, Set<String> wordMap) {
int n = target.length();
int max = 0;
if (!wordMap.contains(target)) return 0;
for (int i = 0; i < n; i++) {
String current = removeCharAt(target, i);
// increase our depth by 1;
int local = 1 + depthFirstCount(current, wordMap);
// find the max depth recursively.
if (local > max)
max = local;
}
return max;
}
static String removeCharAt(String s, int i) {
StringBuilder buf = new StringBuilder(s);
buf.delete(i, i+1);
return buf.toString();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment