拼写单词 - LeetCode 1160

本文主要是介绍拼写单词 - 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;
}