go語言題解LeetCode1160拼寫單詞示例詳解

更新時(shí)間：2022年12月30日 09:07:02 作者：劉09k11

這篇文章主要為大家介紹了go語言題解LeetCode1160拼寫單詞示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

1160. 拼寫單詞 - 力扣（LeetCode）

給你一份『詞匯表』（字符串?dāng)?shù)組） words 和一張『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼寫出 words 中的某個(gè)『單詞』（字符串），那么我們就認(rèn)為你掌握了這個(gè)單詞。

注意：每次拼寫（指拼寫詞匯表中的一個(gè)單詞）時(shí)，chars 中的每個(gè)字母都只能用一次。

返回詞匯表 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。

提示：

1 <= words.length <= 1000

1 <= words[i].length, chars.length <= 100

所有字符串中都僅包含小寫英文字母

思路分析

先統(tǒng)計(jì)chars中各字母(字符)的個(gè)數(shù)

然后分別統(tǒng)計(jì)words字符串?dāng)?shù)組中的每個(gè)字符串的各個(gè)字母(字符)的個(gè)數(shù)

然后在26個(gè)對(duì)應(yīng)位置作比較

若當(dāng)前word字符串的對(duì)應(yīng)位置字符數(shù)小于等于chars中對(duì)應(yīng)位置字符數(shù)

則記錄當(dāng)前word字符串的長度

將其做為總長度的一部分

依次比較余下的word字符串，重復(fù)前面操作，最終得到總長度(答案)

AC 代碼

class Solution {
    public int countCharacters(String[] words, String chars) {
        int n=chars.length();
        int[] arr=new int[26];
        for(int i=0;i<n;i++){
            arr[chars.charAt(i)-'a']++;
        }
        int res=0;
        for(String word:words){
            int[] arr1=new int[26];
            for(int j=0;j<word.length();j++){
                arr1[word.charAt(j)-'a']++;
            }
            for(int i=0;i<26;i++){
                if(arr1[i]<=arr[i]) {
                    if(i==25) res=res+word.length();
                }else break;
            }
        }
        return res;
    }
}

參考

別人用int[26] 解題思路

友情提示：遇到有提示字符串僅包含小寫（或者大寫）英文字母的題，

都可以試著考慮能不能構(gòu)造長度為26的每個(gè)元素分別代表一個(gè)字母的數(shù)組，來簡化計(jì)算

對(duì)于這道題，用數(shù)組c來保存字母表里每個(gè)字母出現(xiàn)的次數(shù)
如法炮制，再對(duì)詞匯表中的每個(gè)詞匯都做一數(shù)組w，比較數(shù)組w與數(shù)組c的對(duì)應(yīng)位置

如果w中的都不大于c，就說明該詞可以被拼寫出，長度計(jì)入結(jié)果
如果w其中有一個(gè)超過了c，則說明不可以被拼寫，直接跳至下一個(gè)（這里用到了帶label的continue語法）

代碼

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] c = new int[26];
        for(char cc : chars.toCharArray()) {
            c[(int)(cc - 'a')] += 1;
        }
        int res = 0;
        a: for(String word : words) {
            int[] w = new int[26];
            for(char ww : word.toCharArray()) {
                w[(int)(ww - 'a')] += 1;
            }
            for(int i=0; i<26; i++) {
                if(w[i] > c[i]) {
                    continue a;
                }
            }
            res += word.length();
        }
        return res;
    }
}

c++幾乎雙百的哈希解法

解題思路

1 構(gòu)建chars的字符到數(shù)量映射表

2. 對(duì)于words里的每個(gè)單詞也構(gòu)建類似一個(gè)表，構(gòu)建后去遍歷比較是否小于等于chars里的數(shù)量，否則失敗

代碼

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        // 記錄累計(jì)的長度之和
        int res = 0;
        // 構(gòu)建chars的映射表
        int cnt[26];
        memset(cnt, 0, sizeof(int)*26);
        for (char c : chars)
        {
            ++cnt[c-'a'];
        }
???????        // 遍歷words去構(gòu)建每個(gè)映射表，然后比較即可
        int curr[26];
        for (string word : words)
        {
            memset(curr, 0, sizeof(int)*26);
            for (char c : word)
            {
                ++curr[c-'a'];
            }
            bool IsOK= true;
            for (int i = 0; i < 26; ++i)
            {
                if (curr[i] > cnt[i])
                {
                    IsOK = false;
                    break;
                }
            }
            if (IsOK)
            {
                res += word.size();
            }
        }
        return res;
    }
};

以上就是go語言題解LeetCode1160拼寫單詞示例詳解的詳細(xì)內(nèi)容，更多關(guān)于go題解拼寫單詞的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: