Buttercola: Zenefits: [OA] Longest Chain

Buttercola: Zenefits: [OA] Longest Chain
给定一个词典， 对于里面单词删掉任何一个字母，如果新单词还在词典里，就形成一个 chain：old word -> new word, 求最长长
比如给List<String> dict = {a,ba,bca,bda,bdca} 最长是4：bdca->bda->ba->a；

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;

    }

}

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


1. Longest Chain
给定一个词典， 对于里面单词删掉任何一个字母，如果新单词还在词典里，就形成一个 chain：old word -> new word, 求最长长
比如给List<String> dict = {a,ba,bca,bda,bdca} 最长是4：bdca->bda->ba->a；


我用的map<Integer (length)，set<String>> 先字典里的词放到map里，然后从最长的词的set里开始recursive call，直到搜到长度是1的里面或者找不到了，int变量记录最长结果。
http://www.1point3acres.com/bbs/thread-145290-1-1.html
        int longest_chain(String[] w) {
        int len = w.length;
        if (len == 0) return 0;
        Queue<String> cBuf = new LinkedList();
        Map<Integer, Set<String>> allWd = new HashMap();
        int maxLen = 0;
        int maxCLen = 0;
        // find the longest length of strings in w
        for (int i = 0; i < w.length; i++){
            int curLen = w[i].length();
            maxLen = Math.max(maxLen, curLen);
            if (allWd.containsKey(curLen)) allWd.get(curLen).add(w[i]);
            else{
                Set<String> curSet = new HashSet();
                curSet.add(w[i]);
                allWd.put(curLen, curSet);
            }
        }
        // search from certain length of words
        for (int i = maxLen; i > maxCLen; i--){
            cBuf = new LinkedList(allWd.get(i));
            // start from initial set of words to search for chain
            int clen = 0;
            while (!cBuf.isEmpty()){
                clen++;
                Set<String> nextSet = allWd.get(i - clen);
                if (nextSet == null) break;
                int count = cBuf.size();
                for (int h = 0; h < count; h++){
                    String t = cBuf.poll();
                    // get next string by deleting one letter
                    for (int l = 0; l < t.length(); l++){
                        String tt = t.substring(0, l) + t.substring(l + 1);
                        if (nextSet.contains(tt)){
                            cBuf.offer(tt);
                            nextSet.remove(tt);
                        }
                    }
                }
            }
            maxCLen = Math.max(maxCLen, clen);
            i -= Math.max(clen - 1, 0);
        }
        return maxCLen;
    }
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=142124&highlight=zenefits
Read full article from Buttercola: Zenefits: [OA] Longest Chain