You are given two 0-indexed arrays of strings startWords
and targetWords
. Each string consists of lowercase English letters only.
For each string in targetWords
, check if it is possible to choose a string from startWords
and perform a conversion operation on it to be equal to that from targetWords
.
The conversion operation is described in the following two steps:
- Append any lowercase letter that is not present in the string to its end.
- For example, if the string is
"abc"
, the letters'd'
,'e'
, or'y'
can be added to it, but not'a'
. If'd'
is added, the resulting string will be"abcd"
.
- For example, if the string is
- Rearrange the letters of the new string in any arbitrary order.
- For example,
"abcd"
can be rearranged to"acbd"
,"bacd"
,"cbda"
, and so on. Note that it can also be rearranged to"abcd"
itself.
- For example,
Return the number of strings in targetWords
that can be obtained by performing the operations on any string of startWords
.
Note that you will only be verifying if the string in targetWords
can be obtained from a string in startWords
by performing the operations. The strings in startWords
do not actually change during this process.
Example 1:
Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"] Output: 2 Explanation: - In order to form targetWords[0] = "tack", we use startWords[1] = "act", append 'k' to it, and rearrange "actk" to "tack". - There is no string in startWords that can be used to obtain targetWords[1] = "act". Note that "act" does exist in startWords, but we must append one letter to the string before rearranging it. - In order to form targetWords[2] = "acti", we use startWords[1] = "act", append 'i' to it, and rearrange "acti" to "acti" itself.
Example 2:
Input: startWords = ["ab","a"], targetWords = ["abc","abcd"] Output: 1 Explanation: - In order to form targetWords[0] = "abc", we use startWords[0] = "ab", add 'c' to it, and rearrange it to "abc". - There is no string in startWords that can be used to obtain targetWords[1] = "abcd".
Constraints:
1 <= startWords.length, targetWords.length <= 5 * 104
1 <= startWords[i].length, targetWords[j].length <= 26
- Each string of
startWords
andtargetWords
consists of lowercase English letters only. - No letter occurs more than once in any string of
startWords
ortargetWords
.
Solution: Bitmask w/ Hashtable
Since there is no duplicate letters in each word, we can use a bitmask to represent a word.
Step 1: For each word in startWords, we obtain its bitmask and insert it into a hashtable.
Step 2: For each word in targetWords, enumerate it’s letter and unset 1 bit (skip one letter) and see whether it’s in the hashtable or not.
E.g. for target word “abc”, its bitmask is 0…0111, and we test whether “ab” or “ac” or “bc” in the hashtable or not.
Time complexity: O(n * 26^2)
Space complexity: O(n * 26)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: int wordCount(vector<string>& startWords, vector<string>& targetWords) { unordered_set<int> s; auto getKey = [](const string& s) { return accumulate(begin(s), end(s), 0, [](int key, char c) { return key | (1 << (c - 'a')); }); }; for (const string& w : startWords) s.insert(getKey(w)); return accumulate(begin(targetWords), end(targetWords), 0, [&](int ans, const string& w) { const int key = getKey(w); return ans + any_of(begin(w), end(w), [&](char c) { return s.count(key ^ (1 << (c - 'a'))); }); }); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment