2135. Count Words Obtained After Adding a Letter
Description
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
.
Solutions
Solution 1: Hash Table + Bit Manipulation
We notice that the given strings only contain lowercase letters, and each letter in a string appears at most once. Therefore, we can represent a string with a binary number of length $26$, where the $i$-th bit being $1$ indicates that the string contains the $i$-th lowercase letter, and $0$ indicates the absence of the $i$-th lowercase letter.
We can convert each string in the array $\textit{startWords}$ into a binary number and store these binary numbers in a set $\textit{s}$. For each string in the array $\textit{targetWords}$, we first convert it into a binary number, then enumerate each letter in this string, remove this letter from the binary number, and check if there exists a binary number in the set $\textit{s}$ such that the XOR result of this binary number with the removed letter's binary number is in the set $\textit{s}$. If such a binary number exists, then this string can be obtained by performing a transformation operation on some string in $\textit{startWords}$, and we increment the answer by one. Then, we skip this string and continue processing the next string.
The time complexity is $O(n \times |\Sigma|)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string array $\textit{targetWords}$, and $|\Sigma|$ is the size of the character set in the string, which is $26$ in this problem.
1 2 3 4 5 6 7 8 9 10 11 |
|
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 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|