ShortestCompletingWord [source code]

public class ShortestCompletingWord {
static
/******************************************************************************/
class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        // Count LICENSE with a map
        Map<Character, Integer> licenseCounts = new HashMap<> ();
        for (char c : licensePlate.toCharArray ()) {
            if (Character.isLetter (c)) {
                Character key = Character.toLowerCase (c);
                licenseCounts.put (key, licenseCounts.getOrDefault (key, 0) + 1);
            }
        }
        // RES has to be initialized to something long enough
        String res = licensePlate + licensePlate;
        // Count each word with a char-indexed array to make reversed lookup during checkCounts easier
        int[] wordCounts = new int[26];
        for (String word : words) {
            Arrays.fill (wordCounts, 0);
            for (char c : word.toCharArray ())
                wordCounts[Character.toLowerCase (c) - 'a']++;
            if (checkCounts (licenseCounts, wordCounts) && word.length () < res.length ())
                res = word;
        }
        return res;
    }

    /* Check whether this word has enough counts to complete LICENSE */
    public boolean checkCounts (Map<Character, Integer> licenseCounts, int[] wordCounts) {
        for (Character c : licenseCounts.keySet ()) {
            if (licenseCounts.getOrDefault (c, 0) > wordCounts[c - 'a'])
                return false;
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ShortestCompletingWord.Solution tester = new ShortestCompletingWord.Solution();
        String[][] inputs = {
            {"1s3 PSt"}, {"step","steps","stripe","stepple"}, {"steps"},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            String licensePlate = inputs[3 * i][0], ans = inputs[3 * i + 2][0];
            String[] words = inputs[3 * i + 1];
            System.out.println (Printer.separator ());
            String output = tester.shortestCompletingWord (licensePlate, words);
            System.out.printf ("%s and [%s] -> %s, expected: %s\n",
                licensePlate, Printer.array (words), Printer.wrapColor (output, output.equals (ans) ? "green" : "red"), ans
            );
        }
    }
}

题意倒是很简单明了, 不过没有什么思路. 还是先笔算笨办法开始;

想不出什么特别好的办法, 还是用笨办法来做; again, Google, 注意Corner Case;

最后有惊无险的做出来了, 速度是26ms (NA). 因为题目对于input给的限定非常的详细, 所以最后实际上也没有太多需要注意的地方;

这题我自己一个小技巧就是, 在count license的时候, 用的是Map, 但是在count word的时候, 用array来做, 因为后面我们要对word的count进行一个反向查询(indexed by letter), 所以用array更加方便; 而license的count用Map是因为我们后面对Map的iterate其实是一个by size, 所以用Map对于sparse的处理会更有利一些;

当然, 如果license count也用array, 最后OJ给的速度很可能会更好一些, 毕竟其实我们要count的东西还是限定在26个字母里面的, 不过总体上来说我觉得用Map的话, 背后的想法更加稳健;

multiple break

另外一个问题, 注意到我这里把check单独拿出来, 是因为假如我把这个函数的body放在上面调用的地方, 你可以看到一个问题, 加入我check失败的时候, 我希望break掉的其实是上层循环, 但是这个没有办法做到, java的break一次只能break一层; 对于这个问题, 以前总结出来过几种做法;

• check terminating index: 也就是说内层循环用index控制, 然后循环里面不加premature return; 当最后terminate的时候, 检查一下这个index, 看一下是不是全部走完了, 这样就知道循环过程当中有没有出现过异常情况;
  • 类似这种做法, 也可以不用index, 而用一个类似res的东西来记录; 只有在需要premature exit的时候才更新这个res, which is initialized to a special value; 这样循环结束的时候检查一下res有没有被更新过就行了;
• separate function: 这里这个东西, 其实也是可以用上面index的方法来做, 不过就显得笨重一点; 另外一个方法就是把内层循环整个都factor出去成为一个返回值是boolean的函数; 这样在这个函数本身的内部因为就只有一个循环, 所以可以方便的用premature return;

Editorial

class Solution {  
    public String shortestCompletingWord(String licensePlate, String[] words) {  
        int[] target = count(licensePlate);  
        String ans = "";  
        for (String word: words)  
            if ((word.length() < ans.length() || ans.length() == 0) &&  
                    dominates(count(word.toLowerCase()), target))  
                ans = word;  
        return ans;  
    }  

    public boolean dominates(int[] count1, int[] count2) {  
        for (int i = 0; i < 26; ++i)  
            if (count1[i] < count2[i])  
                return false;  
        return true;  
    }  

    public int[] count(String word) {  
        int[] ans = new int[26];  
        for (char letter: word.toCharArray()){  
            int index = Character.toLowerCase(letter) - 'a';  
            if (0 <= index && index < 26)  
                ans[index]++;  
        }  
        return ans;  
    }  
}

总体的思路是类似的; 不过他没有用Map而已;

submission和discussion基本没看到新货; 不知道这个题目的downvote为什么这么多;

Problem Description

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, "P" on the licensePlate still matches "p" on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair" does not complete the licensePlate, but the word "supper" does.

Example 1:

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]  
Output: "steps"  
Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".  
Note that the answer is not "step", because the letter "s" must occur in the word twice.  
Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:

Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]  
Output: "pest"  
Explanation: There are 3 smallest length words that contains the letters "s".  
We return the one that occurred first.

Note:

• licensePlate will be a string with length in range [1, 7].
• licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
• words will have a length in the range [10, 1000].
• Every words[i] will consist of lowercase letters, and have length in range [1, 15].

Difficulty:Medium
Total Accepted:3.5K
Total Submissions:6.5K
Contributor:TopCoder111
Companies
google
Related Topics
hash table

Hint 1
Count only the letters (possibly converted to lowercase) of each word. If a word is shorter and the count of each letter is at least the count of that letter in the licensePlate, it is the best answer we've seen yet.