python 字符串遍历_LeetCode基础算法题第159篇：找出由特定字符数组组成的字符串...

技术提高是一个循序渐进的过程，所以我讲的leetcode算法题从最简单的level开始写的，然后到中级难度，最后到hard难度全部完。目前我选择C语言，Python和Java作为实现语言，因为这三种语言还是比较典型的。由于篇幅和精力有限，其他语言的实现有兴趣的朋友请自己尝试。如果有任何问题可以在文章后评论或者私信给我。如果有朋友希望我讲些其他话题，请在评论区留言或者私信给我。持续分享，敬请关注。

LeetCode 1160. 找出由特定字符数组组成的字符串(Find Words That Can Be Formed by Characters)

问题描述：

给定一个字符串数组words和字符串chars。如果字符串可以由chars内的字符组成(每个字符只能使用一次)，那么它就是一个good字符串。返回words中所有good的字符串的长度的和。

注:

1. 1 <= words.length <= 1000;
2. 1 <= words[i].length, chars.length <= 100;
3. 所有的字符串都仅包含小写字母;

示例：

C语言实现：

显然，我们可以得出一个结论，如果一个字符串中的某个字母在比chars出现的次数多，那么它就不是一个good字符串。

在设计算法的时候，我期望对chars和words中每个单词最多只遍历一次。

因为一个words中的单词是否是一个good字符串，依赖chars里字符的内容和个数。因此首先遍历chars，统计里面字符的内容及其个数，结果存放到一个数组中。我们将这个数组比作原料仓库。

然后遍历words中的每个单词w。对于每个w，按照w中字符组合顺序，从原料仓库count中一个个的拿出字符，如果发现需要的字符在count中库存为0的时候，那么w就不是good字符串。

这里注意count数组在遍历每个w的过程中，内容可能会发生改变，但是遍历之前是原封不动的。

所以这就需要为每个w遍历创建一个count的副本。因此需要创建len(words)个副本，这是我觉得这个方法不太好的地方。如果能省去这一过程，算法效率会有很大提升，大家不妨思考思考。

详细代码如下：

Java语言实现：

Java 的实现和C语言的实现一致，不再撰述。

代码如下：

Python语言实现：

Python 的实现和C语言的实现一致，不再撰述。

代码如下：

另一个简单的实现是用Counter，只需要两行，但是实际测试的结果，效率比较差。

count = Counter(chars)return sum([ len(w) for w in words: if not Counter(w)-count ])

---