文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你兩個下標從 0 開始的字符串數(shù)組 startWords 和 targetWords 。每個字符串都僅由 小寫英文字母 組成。

對于 targetWords 中的每個字符串，檢查是否能夠從 startWords 中選出一個字符串，執(zhí)行一次 轉換操作 ，得到的結果與當前 targetWords 字符串相等。

轉換操作 如下面兩步所述：

• 追加 任何 不存在 于當前字符串的任一小寫字母到當前字符串的末尾。
  例如，如果字符串為 “abc” ，那么字母 ‘d’、‘e’ 或 ‘y’ 都可以加到該字符串末尾，但 ‘a(chǎn)’ 就不行。如果追加的是 ‘d’ ，那么結果字符串為 “abcd” 。
• 重排 新字符串中的字母，可以按 任意 順序重新排布字母。
  例如，“abcd” 可以重排為 “acbd”、“bacd”、“cbda”，以此類推。注意，它也可以重排為 “abcd” 自身。

找出 targetWords 中有多少字符串能夠由 startWords 中的 任一 字符串執(zhí)行上述轉換操作獲得。返回 targetWords 中這類 字符串的數(shù)目 。

注意：你僅能驗證 targetWords 中的字符串是否可以由 startWords 中的某個字符串經(jīng)執(zhí)行操作獲得。startWords 中的字符串在這一過程中 不 發(fā)生實際變更。

示例 1： 輸入：startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"] 輸出：2 解釋： - 為了形成 targetWords[0] = "tack" ，可以選用 startWords[1] = "act" ，追加字母 'k' ，并重排 "actk" 為 "tack" 。 - startWords 中不存在可以用于獲得 targetWords[1] = "act" 的字符串。注意 "act" 確實存在于 startWords ，但是 必須 在重排前給這個字符串追加一個字母。 - 為了形成 targetWords[2] = "acti" ，可以選用 startWords[1] = "act" ，追加字母 'i' ，并重排 "acti" 為 "acti" 自身。示例 2： 輸入：startWords = ["ab","a"], targetWords = ["abc","abcd"] 輸出：1 解釋： - 為了形成 targetWords[0] = "abc" ，可以選用 startWords[0] = "ab" ，追加字母 'c' ，并重排為 "abc" 。 - startWords 中不存在可以用于獲得 targetWords[1] = "abcd" 的字符串。提示： 1 <= startWords.length, targetWords.length <= 5 * 10^4 1 <= startWords[i].length, targetWords[j].length <= 26 startWords 和 targetWords 中的每個字符串都僅由小寫英文字母組成 在 startWords 或 targetWords 的任一字符串中，每個字母至多出現(xiàn)一次

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-words-obtained-after-adding-a-letter
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

2. 解題

• 將 startwords 里的單詞轉成 26 位 int 數(shù)字，再添加一個不存在的 bit 進去，所有的情況存到 哈希 里
• 遍歷 targetword 里的單詞轉成 int ，在哈希里能查到就可以轉換

class Solution { public:int wordCount(vector<string>& startWords, vector<string>& targetWords) {unordered_set<int> set;for(auto& s : startWords){int num = 0;for(auto c : s)num |= 1<<(c-'a');for(int i = 0; i < 26; ++i){if((num&(1<<i))==0)//添加了不存在的字母{set.insert(num | (1<<i));}}}int ans = 0;for(auto& s : targetWords){int num = 0;for(auto c : s)num |= 1<<(c-'a');if(set.find(num) != set.end())ans++;}return ans;} };

460 ms 151.5 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 2135. 统计追加字母可以获得的单词数（位运算+哈希）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。