[Two Sigma OA] Longest Chain

OAds/image/0663.jpg" alt="[Two Sigma OA] Longest Chain"/>

[Two Sigma OA] Longest Chain

题目：

.html

实现：

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));}}

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));}
}

转载于:.html