#2135

Count Words Obtained After Adding a Letter

specialist · 980 · lc medium +32 · verified · 43.9% accepted · 725 likes · top 26%

Description

You are given two 0-indexed arrays of strings startWords and targetWords, each consisting of lowercase English letters only.

For each string in targetWords, determine whether it can be produced from some string in startWords by applying the following two-step conversion:

- Append one lowercase letter that does not already appear in the string.

- For example, if the string is "abc", you could add 'd', 'e', or 'y', but not 'a'. Adding 'd' gives "abcd".

- Rearrange all the letters in any order.

- For example, "abcd" can be rearranged to "acbd", "bacd", "cbda", etc.

Return the number of strings in targetWords that can be obtained this way.

Note that the strings in startWords are not actually modified 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".

Code

1

2

3

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int: