Title:
http://www.1point3acres.com/bbs/thread-131978-1-1.html
realization:
import java.util.*;
/**
* Created by Min on 10/2/2017.
*/
public class LongestChain {
private int getLongestChain(String[] words) {
Map<Integer, Set<String>> map = new HashMap<Integer, Set<String>>();
for (String word : words) {
Set<String> set = map.get(word.length());
if (set == null) {
set = new HashSet<String>();
map.put(word.length(), set);
}
set.add(word);
}
int ans = 0;
List<Integer> lengthList = new ArrayList<Integer>(map.keySet());
Collections.sort(lengthList, Collections.reverseOrder());
return helper(0, lengthList, map, "");
}
private int helper(int start, List<Integer> list, Map<Integer, Set<String>> map, String prev) {
if (start == list.size()) {
return 0;
}
int ans = 0;
if (start == 0) {
for (String word : map.get(list.get(0))) {
ans = Math.max(ans, helper(start + 1, list, map, word) + 1);
}
} else if (prev.length() -1 == list.get(start)) {
Set<String> wordSet = map.get(list.get(start));
for (int i = 0; i < prev.length(); i++) {
String newWord = prev.substring(0, i) + prev.substring(i + 1);
if (wordSet.contains(newWord)) {
wordSet.remove(newWord);
ans = Math.max(ans, helper(start + 1, list, map, newWord) + 1);
}
}
}
return ans;
}
public static void main(String[] args) {
String[] input = {"a","ba","bca","bda","bdca"};
LongestChain solution = new LongestChain();
System.out.println(solution.getLongestChain(input));
}
}
[UNK]
import java.util.*;
/**
* Created by Min on 10/2/2017.
*/
public class LongestChain2 {
public int getLongestChain(String[] words) {
Set<String> set = new HashSet<String>();
for (String word : words) {
set.add(word);
}
HashMap<String, Integer> map = new HashMap<String, Integer>();
int ans = 0;
for (String word : words) {
Integer length =map.get(word);
if (length == null) {
length = dfs(word, map, set);
}
ans = Math.max(ans, length);
}
return ans;
}
private int dfs(String word, Map<String, Integer> map, Set<String> set) {
Integer ans = map.get(word);
if (ans != null) {
return ans.intValue();
}
ans = 0;
for (int i = 0; i < word.length(); i++) {
String newWord = word.substring(0, i) + word.substring(i + 1);
ans = Math.max(ans, dfs(newWord, map, set) + 1);
}
map.put(word, ans);
return ans.intValue();
}
public static void main(String[] args) {
String[] input = {"a","ba","bca","bda","bdca"};
LongestChain2 solution = new LongestChain2();
System.out.println(solution.getLongestChain(input));
}
}
Reproduced in: https://www.cnblogs.com/Gryffin/p/7623249.html