LeetCode-HashMap-748.Shortest Completing Word

本文主要是介绍LeetCode-HashMap-748.Shortest Completing Word，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本打算LeetCode一刷结束后，借阅大神的答案二刷再处理文博文，但这道题提交了5次才对，期间有不少粗心的地方，写出来长点记性。

1. 题干：

https://leetcode.com/problems/shortest-completing-word/description/
给出一系列单词（String[] words），以及一个参照（letter）。找出一个最短的单词，该单词包含参照中所有字母【注意，仅仅是字母】
忽略大小写
允许重复
这里写图片描述

2.版本一的思路：

字符串筛选出字母，全改为小写
字符串数组按长短排序
将单词的字符存入哈希表，然后进行匹配比较
注意大小写、允许重复、删除问题、使用数组其实思路简单【题分类为哈希表，没写数组的，不知道哪个效率高，总之我认为此版本效率一般吧】

错误：
1. 第一次用了不稳定的选择排序
2. 第二次冒泡的第二层-2，第一第二都应该-1才对
3.
这里写图片描述

原因：num计数器位置不对，删除不成功。应该放置在迭代器后，也就是说每次都应该重置为0
4.
这里写图片描述

原因：置为0后再依次加1导致的，删除不成功（yes中，第一次成功删除e，第二次想在下标为1处删除s，显然失败）
解决办法：替换——匹配到的所有字符，都替换为空格，因为信中数字已经剔除干净

代码

package HashTable;import java.util.HashMap;
import java.util.Iterator;/*** @author 王海[https://github.com/AtTops]* @package HashTable* @description* @Date 2018/2/22 10:42* @Version V1.0*/
public class ShortestCompletWord {public static String shortestCompletingWord(String licensePlate, String[] words) {
//        1. 去掉所有非字母字符并转小写String letter = licensePlate.replaceAll("[^a-z^A-Z]", "").toLowerCase();
//        char[] chars = doSomething.toCharArray();
//        Arrays.sort(chars);
//        String letter = chars.toString();//        2. 字符串数组按长短排序(选择排序可能会改变相同长度的单词的出现顺序，这里不能用不稳定排序)String temp;
//        选择排序：错误
/*        for (int i = 0; i < words.length; i++) {for (int j = i + 1; j < words.length; j++) {if (words[i].length() > words[j].length()) {temp = words[i];words[i] = words[j];words[j] = temp;}}}*/
//      冒泡：小的往上int n = words.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - 1; j++) {if (words[j].length() > words[j+1].length()) {temp = words[j];words[j] = words[j+1];words[j+1] = temp;}}}for (int i = 0; i < words.length; i++) {System.out.println(words[i]);
//                如果比验证信短，则无需继续本次循环了if (words[i].length() < letter.length()) {continue;}String lowerWord = words[i].toLowerCase();//        3. 将单词字符存入哈希表HashMap<Integer, Character> wordMap = new HashMap<>(4, 1);for (int j = 0; j < lowerWord.length(); j++) {wordMap.put(j, lowerWord.charAt(j));}
//          4. 返回第一个包含信所有字符的单词int count = 0;for (int k = 0; k < letter.length(); k++) {if (!wordMap.containsValue(letter.charAt(k))) {break;}
/*for (int m = 0; m < wordMap.size(); k++){if (wordMap.get(m).equals(letter.charAt(k))) {
//                    删除该匹配成功的字符，因为可能需要多个该字符(所以使用containsValue会比较麻烦)wordMap.replace(num, ' ');count++;break;}}*/Iterator itor = wordMap.values().iterator();int num = 0;while (itor.hasNext()) {if ((char) itor.next() == letter.charAt(k)) {
//                    替换该匹配成功的字符，因为可能需要多个该字符wordMap.replace(num, ' ');count++;break;} else {num++;}}}if (count == letter.length()) {return words[i];}}return "Oh no! SomeThing wrong!!!";}public static void main(String[] args) {
//        String[] words = {"s", "sFsfa", "ssF","sFs", "asf", "ssss"};
//        String result = shortestCompletingWord(" sSfa5552 ", words);String[] words = {"yes","less","see"};String result = shortestCompletingWord("ESs69865", words);System.out.println(result);}
}