这是悦乐书的第 309 次更新, 第 330 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 178 题(顺位题号是 748). 从给定的字典单词中查找最小长度单词, 其中包含字符串 licensePlate 中的所有字母. 据说这样的单词可以完成给定的字符串 licensePlate. 在这里, 对于字母我们忽略大小写. 例如, licensePlate 上的 "P" 仍与单词上的 "p" 匹配. 答案肯定存在. 如果有多个答案, 则返回数组中首先出现的答案. licensePlate 可能会多次出现相同的字母. 例如, 给定 licensePlate 为 "PP", 单词 "pair" 不会完成 licensePlate, 但单词 "supper" 会完成. 例如:
输入: licensePlate ="1s3 PSt",words = ["step","steps","stripe","stepple"]
输出:"steps"
说明: 包含字母 "S","P","S" 和 "T" 的最小长度字. 请注意, 答案不是 "step", 因为字母 "s" 必须出现在单词中两次. 另请注意, 为了比较单词中是否存在字母, 我们忽略了大小写.
输入: licensePlate ="1s3 456",words = ["look","pest","stew","show"]
输出:"pest"
说明: 有 3 个最小长度的单词, 包含字母 "s". 我们返回先出现的那个.
注意:
licensePlate 将是一个长度在 [1,7] 范围内的字符串.
licensePlate 将包含数字, 空格或字母(大写或小写).
数组的长度范围为[10,1000].
每个 words[i]将由小写字母组成, 并且长度在 [1,15] 范围内.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
给定的 licensePlate 中包含数字, 空格或大写字母, 而比较时是忽略大小写的, 所以我们先将 licensePlate 中的字母抽出来, 并且将里面的大写字母转为小写, 变成一个新的字符串. 然后开始遍历 words 数组, 比较数组的当前元素和前面得到的新字符串的关系, 判断此单词是否能够由新字符串组成, 在此将判断的方法独立处理, 判断的方法是借助容量为 26 的整数数组, 新字符串中有的字母, 此单词中必须要有, 否则就返回 false.
- public String shortestCompletingWord(String licensePlate, String[] words) {
- String s = "";
- for (char ch : licensePlate.toCharArray()) {
- if ((ch>= 'a' && ch <= 'z') || (ch>= 'A' && ch <= 'Z')) {
- s += ch;
- }
- }
- s = s.toLowerCase();
- String res = "";
- for (String str : words) {
- if ((res.isEmpty() || res.length()> str.length()) && isContains(s, str)) {
- res = str;
- }
- }
- return res;
- }
- /**
- * 判断此单词是否全部包含新字符串中的字母
- * @param s licensePlate 中英文字母组成的字符串
- * @param s2 words 中的每个单词
- * @return
- */
- public boolean isContains(String s, String s2) {
- int[] arr = new int[26];
- // 将单词中的字母出现次数记数
- for (char ch : s2.toCharArray()) {
- arr[ch-'a']++;
- }
- for (char ch : s.toCharArray()) {
- // 新字符串中的当前字母在单词中不存在
- if (arr[ch-'a'] == 0) {
- return false;
- }
- arr[ch-'a']--;
- }
- return true;
- }
03 第二种解法
我们也可以将辅助方法融合到主方法中去. 依旧是先将 licensePlate 里的字母抽出来, 存入一个容量 26 的数组中, 此处多使用了一个变量来记录新字符串中字母的总数量. 然后开始循环处理 words 中的元素, 每次循环都需要将数组和总数量复制一份, 然后去做判断, 判断的逻辑和上面第一种解法的思路类似.
- public String shortestCompletingWord2(String licensePlate, String[] words) {
- int[] arr = new int[26];
- int count = 0;
- for (char ch : licensePlate.toCharArray()) {
- if (ch>= 'a' && ch <= 'z') {
- arr[ch-'a']++;
- count++;
- } else if(ch>= 'A' && ch <= 'Z') {
- arr[ch-'A']++;
- count++;
- }
- }
- String result = "";
- for (String str : words) {
- int temp = count;
- int[] copy = arr.clone();
- for (char ch : str.toCharArray()) {
- if (--copy[ch-'a']>= 0) {
- temp--;
- }
- }
- if (temp == 0 && (result.isEmpty() || result.length()> str.length())) {
- result = str;
- }
- }
- return result;
- }
04 小结
算法专题目前已日更超过五个月, 算法题文章 178 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/2da8bba813f4