leetcode1160：拼接单词

问题描述

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的长度之和。

示例 1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

提示：

1.1 <= words.length <= 1000
2.1 <= words[i].length, chars.length <= 100
3.所有字符串中都仅包含小写英文字母

题解

说下让我看起来非常惊艳的解法，通过26位ASCII编码属性计算每个字母的count数量，然后通过words循环内的元素和chars数组进行对比，最后return满足条件的长度就好了，废话不多说，上代码：

/**
    * 
    * @param words
    *          单词数组
    * @param chars
    *          已有字母
    * @return
    */
   public int countCharacters(String[] words, String chars) {
       int[] originalCounter = counter(chars);
       int length = 0;
       for (int i = 0; i < words.length; i++) {
           String word = words[i];
           int[] wordCounter = counter(word);
           boolean isSuccess = true;
           for (int j = 0; j < 26; j++) {
               if (originalCounter[j] < wordCounter[j]) {
                   isSuccess = false;
                   break;
               }
           }
           if (isSuccess) {
               length += word.length();
           }
       }

       return length;
   }

   /**
    * 将字符转为索引对应的ASCII码值
    * 
    * @param word
    * @return
    */
   private int[] counter(String word){
       int[] counter = new int[26];
       char[] charArray = word.toCharArray();
       for (int j = 0; j < charArray.length; j++) {
           counter[charArray[j] - 'a'] ++; // 这里是关键哦
       }
       return counter;
   }

思路还是挺好的，但是上面的代码有些冗余有没有发现，正好通过这次刷题，学到了continue 标签;这种写法，意义在于使内层循环break，外层继续下次遍历，代码如下：

public int countCharacters(String[] words, String chars) {
        int[] ch_array = new int[26];
        for (char c : chars.toCharArray()) {
            ++ch_array[c - 'a'];
        }
        int length = 0;
        search:
        for (String word : words) {
            int[] word_count = new int[26];
            for (char c : word.toCharArray()) {
                if (++word_count[c - 'a'] > ch_array[c - 'a']) {
                    continue search;
                }
            }
            length += word.length();
        }
        return length;
    }

2020-04-20

leetcode40：TOP k，快排算法

leetcode

leetcode1160：拼接单词

问题描述

题解

评论

标签

分类

归档

最新文章

Your browser is out-of-date!