拼写单词 - LeetCode 1160 - 附C++代码

一、问题描述

        给你一份『词汇表』（字符串数组） 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。

原题：LeetCode 1160. 拼写单词

二、思路分析

1、暴力法

        分析题意中的判定条件，“会一个单词word”可以转换为条件：对word中的每一个字母，都有一个chars中的、未使用过的字母与之对应。由此不难想到暴力法的求解思路：每当判定一个word，创建一个与chars的每位对应的标记数组Mark[chars.size()]，用于标记chars对应位是否被使用过，然后遍历word中的每一个字母，从chars中查找未用过的相同字母，并相应维护Mark，若word中的每一个字母都能取到，则认为“会”，结果长度增加该单词长度。

2、优化方式1

        分析暴力法的求解，有大量时间花费在了从chars中查找相同字母的操作上，为了优化这步查找，可以对chars建立索引，由于chars中的字母不能重复使用，可以建立<字母，个数>的map<char,int>。查找一个单词时，拷贝一份chars的map，再遍历这个单词中的字母，查找到字母的同时将可用个数减1。倘若未出现个数不够的情况，则认为“会这个单词”。

3、优化方式2

        根据 2 中的思路，已经对chars建立了map，进一步地，我们可以对每一个word也建立相同类型的map，同时无需再次拷贝chars的map，“会这个单词”则转换为条件：word中的每一个字母（即word_map中的每一个key），chars中都有足够的“可用量”（即chars_map[key]足够大）。

三、代码实现

1、暴力法

        略。

2、优化方式1（chars的map重复拷贝）

class Solution1 {
public:int countCharacters(vector<string>& words, string chars) {int res_len = 0;bool miss = false;//Get chars's index map <char,num>.map<char, int> chars_map;for (char ch : chars) {if (chars_map.count(ch)) chars_map[ch]++;else chars_map[ch] = 1;}//Judge each word in words.for (string word : words) {//Copy one map.map<char, int> copy_map(chars_map);miss = false;//Count one word.for (char ch : word) {if (!copy_map.count(ch) || copy_map[ch] == 0) {miss = true;break;}copy_map[ch]--;}if (!miss) res_len += word.size();}return res_len;}
};int main()
{/** 解题思路：本题转换成查找模型，对words中的每个单词，查找chars中是否存在一一对应；* 思路1：为了快速进行查找，对chars建立索引，由于chars中的字母不能重复使用，可以建立<字母，个数>的map<char,int>遍历一遍chars，建立索引map，每找到对应的字母，将对应的int+1；判断一个Word时，拷贝一份map，每当遇到一个字母，map中对应可用个数-1；当遇到剩余可用个数不足时，认为不会，若全部字母个数都够，则认为会。*/cout << "Process start." << endl;Solution1 s;vector<string> words1 = { "cat","bt","hat","tree" };string chars1 = "atach";cout << "Excepted result1 is : 6    Actually result1 is : " << s.countCharacters(words1, chars1) << endl;vector<string> words2 = { "hello","world","leetcode" };string chars2 = "welldonehoneyr";cout << "Excepted result2 is : 10    Actually result2 is : " << s.countCharacters(words2, chars2) << endl;cout<< "Process finish." << endl;return 0;
}

3、优化方式2

#include <iostream>
#include <vector>
#include <string>
#include <map>using namespace std;class Solution {
public:int countCharacters(vector<string>& words, string chars) {int res_len = 0;bool miss = false;//Get chars's index map <char,num>.map<char, int> chars_map;for (char ch : chars)chars_map[ch]++;//Judge each word in words.for (string word : words) {//Create word map.map<char, int> word_map;for (char ch : word)word_map[ch]++;//Start to judgemiss = false;for (auto k_v : word_map) {if (k_v.second > chars_map[k_v.first]) {miss = true;break;}}if (!miss) res_len += word.size();}return res_len;}
};int main()
{/** 解题思路：本题转换成查找模型，对words中的每个单词，查找chars中是否存在一一对应；* 思路1：为了快速进行查找，对chars建立索引，由于chars中的字母不能重复使用，可以建立<字母，个数>的map<char,int>遍历一遍chars，建立索引map，每找到对应的字母，将对应的int+1；判断一个Word时，拷贝一份map，每当遇到一个字母，map中对应可用个数-1；当遇到剩余可用个数不足时，认为不会，若全部字母个数都够，则认为会。* 思路2：对每一个word也建立相同类型的map，同时无需再次拷贝chars的map，“会这个单词”则转换为条件：每一个字母（即word_map中的每一个key），chars中都有足够的“可用量”（即chars_map[key]>word_map[key]）。*/cout << "Process start." << endl;Solution s;vector<string> words1 = { "cat","bt","hat","tree" };string chars1 = "atach";cout << "Excepted result1 is : 6    Actually result1 is : " << s.countCharacters(words1, chars1) << endl;vector<string> words2 = { "hello","world","leetcode" };string chars2 = "welldonehoneyr";cout << "Excepted result2 is : 10    Actually result2 is : " << s.countCharacters(words2, chars2) << endl;cout<< "Process finish." << endl;return 0;
}

四、运行结果

1、一个map多次拷贝

2、分别建立map

五、时间与空间复杂度对比

        优化方式2 和 优化方式3 的时间复杂度是O(n1 + n2)，空间复杂度是O(2 * n2)，n1是words的总长度，n2 是chars的长度。但两种方式运行时的区别在哪呢？到底哪个更快？

        从运行信息中显示，对于给定的测试用例，优化方式2 比 优化方式3 内存占用更高，但运行速度更快（这是在我预料之外的），倘若把 3 中的 map 改为 unordered_map，内存占用将会进一步降低，而耗时则会更高。

        分析具体执行的过程，发现有两个点：

        1、给定的大部分用例中，chars的长度都是比单个word长的，这导致方式2 （拷贝chars_map）比方式3 （创建word_map）空间占用更高；

        2、对于一个不会的word，对方式2 而言，并不一定会完整地遍历整个word，只要中间有一个字母出现了问题，这个word的后续字母都将不会被遍历。而对于方式3，一定是完整地遍历这个word的（构建map在判定之前）。这是二者判定耗时上的差别。

        此外，方式2 使用了map 的拷贝构造函数（构建了更多元素），方式3使用insert 方法（插入的元素更少）， 这两种方法到底哪个的性能更高仍待查找资料或者实验确认。