go語言題解LeetCode1160拼寫單詞示例詳解
題目描述
給你一份『詞匯表』(字符串?dāng)?shù)組) words
和一張『字母表』(字符串) chars
。
假如你可以用 chars
中的『字母』(字符)拼寫出 words
中的某個(gè)『?jiǎn)卧~』(字符串),那么我們就認(rèn)為你掌握了這個(gè)單詞。
注意:每次拼寫(指拼寫詞匯表中的一個(gè)單詞)時(shí),chars 中的每個(gè)字母都只能用一次。
返回詞匯表 words
中你掌握的所有單詞的 長(zhǎng)度之和。
示例 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字符串的長(zhǎng)度
將其做為總長(zhǎng)度的一部分
依次比較余下的word字符串,重復(fù)前面操作,最終得到總長(zhǎng)度(答案)
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)造長(zhǎng)度為26的每個(gè)元素分別代表一個(gè)字母的數(shù)組,來簡(jiǎn)化計(jì)算
對(duì)于這道題,用數(shù)組c來保存字母表里每個(gè)字母出現(xiàn)的次數(shù)
如法炮制,再對(duì)詞匯表中的每個(gè)詞匯都做一數(shù)組w,比較數(shù)組w與數(shù)組c的對(duì)應(yīng)位置
如果w中的都不大于c,就說明該詞可以被拼寫出,長(zhǎng)度計(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ì)的長(zhǎng)度之和 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)文章!
相關(guān)文章
go高并發(fā)時(shí)append方法偶現(xiàn)錯(cuò)誤解決分析
這篇文章主要為大家介紹了go高并發(fā)時(shí)append方法偶現(xiàn)錯(cuò)誤解決分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-10-10通過Golang實(shí)現(xiàn)linux命令ls命令(命令行工具構(gòu)建)
這篇文章主要為大家詳細(xì)介紹了如何通過Golang實(shí)現(xiàn)一個(gè)linux命令ls命令(命令行工具構(gòu)建),文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價(jià)值,感興趣的可以了解一下2023-01-01Go語言中GORM存取數(shù)組/自定義類型數(shù)據(jù)
在使用gorm時(shí)往往默認(rèn)的數(shù)據(jù)類型不滿足我們的要求,需要使用一些自定義數(shù)據(jù)類型作為字段類型,下面這篇文章主要給大家介紹了關(guān)于Go語言中GORM存取數(shù)組/自定義類型數(shù)據(jù)的相關(guān)資料,需要的朋友可以參考下2023-01-01Go 循環(huán)結(jié)構(gòu)for循環(huán)使用教程全面講解
這篇文章主要為大家介紹了Go 循環(huán)結(jié)構(gòu)for循環(huán)使用全面講解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-10-10詳解go-zero如何實(shí)現(xiàn)計(jì)數(shù)器限流
這篇文章主要來和大家說說限流,主要包括計(jì)數(shù)器限流算法以及具體的代碼實(shí)現(xiàn),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-08-08Golang實(shí)現(xiàn)Directional Channel(定向通道)
這篇文章主要介紹了Golang實(shí)現(xiàn)Directional Channel(定向通道),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02