LeetCode拼写单词_leetcode 单词合成问题

刷题笔记，随便记一记

题目描述

方法一：构造哈希表

主要思路：给单词表构造一个哈希表，再给单词构造一个哈希表，对比每个字符的大小关系即可

class Solution {
public:
    map<char, int> getWordWap(string word){
        map<char, int> res;//为每个单词以及字母表构造哈希表
        for(char c : word){
            res[c]++;
        }
        return res;
    }

    int countCharacters(vector<string>& words, string chars) {
        map<char, int> table = getWordWap(chars);
        int len = 0;
        for(string word : words){
            bool isForm = true;//字母表中的字符，是否构成此的单词
            map<char, int> mp = getWordWap(word);
            for(char c : word){
                if(mp[c] > table[c]){
                    isForm = false;//字母表中的字符数量不够
                    break;
                }
            }
            if(isForm)  len += word.size(); 
        }
        return len;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

构造了多个哈希表，可想而知，效率不高

方法二：构造数组

思路和方法一差不多，由于字母表最多只有26个小写英文字母，可以通过构造长度为26的数组记录字符个数

class Solution {
public:
    vector<int> getArray(string word){
        vector<int> res(26, 0);
        for(char c : word){
            res[c - 'a']++;
        }
        return res;
    }

    int countCharacters(vector<string>& words, string chars) {
        vector<int> table = getArray(chars);
        int len = 0;
        for(string word : words){
            bool isForm = true;
            vector<int> word_array = getArray(word);
            for(int i=0; i<26; i++){
                if(table[i] < word_array[i]){
                    isForm = false;
                    break;
                }
            }
            if(isForm) len += word.size();
        }
        return len;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28