oracle按特定字符截取字符串_LeetCode基础算法题第159篇：找出由特定字符数组组成的字符串...

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

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

问题描述&＃xff1a;

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

注:

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

示例&＃xff1a;

C语言实现&＃xff1a;

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

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

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

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

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

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

详细代码如下&＃xff1a;

Java语言实现&＃xff1a;

Java 的实现和C语言的实现一致&＃xff0c;不再撰述。

代码如下&＃xff1a;

Python语言实现&＃xff1a;

Python 的实现和C语言的实现一致&＃xff0c;不再撰述。

代码如下&＃xff1a;

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

count &＃61; Counter(chars)return sum([ len(w) for w in words: if not Counter(w)-count ])