Sunday, October 4, 2015

Zenefits: [OA] Longest Chain

给定一个词典, 对于里面单词删掉任何一个字母,如果新单词还在词典里,就形成一个 chain:old word -> new word, 求最长长
比如给List<String> 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<Integer, Set<String>> 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<String> words = new HashSet<>();
                words.add(token);
                map.put(len, words);
            }
            
            maxLen = Math.max(maxLen, len); 
        }
        
        int result = longestWordChainHelper(maxLen, 1, map);
        
        return result;
    }
    
    private static int longestWordChainHelper(int curLen, int level, 
        Map<Integer, Set<String>> dict) {
        if (curLen == 0) {
            return max;
        }
        
        if (dict.containsKey(curLen)) {
            Set<String> words = dict.get(curLen);
            Iterator<String> it = words.iterator();
            while (it.hasNext()) {
                String s = it.next();
                for (int i = 0; i < s.length(); i++) {
                    StringBuffer sb = new StringBuffer(s);
                    sb.deleteCharAt(i);
                    String nextStr = sb.toString();
                    if (dict.containsKey(curLen - 1) && 
                        dict.get(curLen - 1).contains(nextStr)) {
                        longestWordChainHelper(curLen - 1, level + 1, dict);
                    }
                }
                it.remove();
            }        
            max = Math.max(max, level);
        }

        return max;
    }
}

1 comment:

  1. 思路不错,不过有bug,你从maxLen开始算,但如果longestChain不是从maxLen的String开始的,你的code就得不到正确结果,应该loop一下所有的len,当然,如果len已经比longestChain短了,就可以结束了

    ReplyDelete