Buttercola: Zenefits: [OA] Longest Chain

Buttercola: Zenefits: [OA] Longest Chain

给定一个词典， 对于里面单词删掉任何一个字母，如果新单词还在词典里，就形成一个 chain：old word -> new word, 求最长长 比如给List dict = {a,ba,bca,bda,bdca} 最长是4：bdca->bda->ba->a； Code (Java): import java.util.*; public class Solution { private static int max = 0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); String[] dict = new String[n]; for (int i = 0; i < n; i++) { dict[i] = scanner.next(); } int result = longestWordChain(dict); System.out.println(result); scanner.close(); } public static int longestWordChain(String[] dict) { if (dict == null || dict.length == 0) { return 0; } Map> map = new HashMap<>(); // Fill the map int maxLen = 0; for (String token : dict) { int len = token.length(); if (map.containsKey(len)) { map.get(len).add(token); } else { Set words = new HashSet<>(); words.add(token); map.put(len, words); } maxLen = Math.max(maxLen, len); } int result = longestWordChainHelper(maxLen, 1, map); return result;

Read full article from Buttercola: Zenefits: [OA] Longest Chain