#2135

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Words Obtained After Adding a Letter

Given startWords and targetWords, check how many targetWords can be formed by adding one letter and rearranging letters of startWords.

array hash table string bit manipulation sorting

Problem Statement

You are given two 0-indexed arrays of strings, startWords and targetWords. Each string in these arrays consists of lowercase English letters. Your task is to determine how many words from targetWords can be formed by adding exactly one letter to a word from startWords and rearranging its letters.

For each word in targetWords, check if it can be derived by adding one letter to any word in startWords. You can rearrange the letters of the resulting string after adding the letter. The challenge is to implement an efficient solution to handle potentially large inputs.

Examples

Example 1

Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]

Output: 2

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

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 and targetWords consists of lowercase English letters only.
No letter occurs more than once in any string of startWords or targetWords.

Solution Approach

Array Scanning and Hash Lookup

Start by scanning through each word in targetWords. For each targetWord, check if any word in startWords can be transformed into the targetWord by adding exactly one letter. Using a hash table can help to quickly check for the presence of valid startWords after one letter is added and rearranged.

Letter Addition and Rearrangement Check

For each startWord, generate all possible words by adding one letter to it. After the letter is added, check if the new word can be rearranged to form any word in targetWords. Sorting both the startWord and targetWord can help to efficiently compare the transformed words.

Optimizing with Hash Tables

Store the sorted startWords in a hash table to improve lookup efficiency. This allows you to check if a potential transformation of a targetWord (after adding one letter and rearranging) exists in startWords in constant time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the method used for checking the transformation of each targetWord. A basic approach would involve generating all potential transformations and checking them against startWords, resulting in a time complexity of O(n * m * log m), where n is the length of targetWords and m is the length of the longest word. Using a hash table to store sorted startWords can improve the lookup time to O(1), reducing the overall complexity to O(n * m). The space complexity is O(n * m) due to the storage of sorted startWords and temporary transformations.

What Interviewers Usually Probe

Tests the candidate's understanding of efficient string manipulation and hash table usage.
Focuses on the candidate's ability to optimize array scanning and string transformations.
Evaluates problem-solving skills involving letter addition and checking rearrangements.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the fact that only one letter can be added to the startWord.
Inefficient implementation by directly comparing unsorted strings instead of using sorting or hash-based lookups.
Overlooking the need for handling large inputs efficiently, which could lead to time limit exceeded errors.

Follow-up variants

Consider variations where more than one letter can be added to the startWord.
Allow multiple transformations per word in startWords to generate multiple valid targetWords.
Change the constraints to allow words of varying lengths to test performance with larger inputs.

FAQ

What is the primary challenge of the "Count Words Obtained After Adding a Letter" problem?

The primary challenge is efficiently checking if a word from targetWords can be formed by adding one letter to a word from startWords and rearranging it.

How can hash tables improve the solution for this problem?

By storing the sorted versions of startWords in a hash table, you can quickly check if a transformed targetWord exists, significantly reducing lookup time.

Can the solution handle large inputs effectively?

Yes, by utilizing efficient data structures like hash tables and limiting unnecessary computations, the solution can handle large inputs within time constraints.

How do I optimize the rearrangement step in the solution?

Sort both the targetWord and the transformed startWord after adding a letter to easily compare them and check if they are anagrams of each other.

What should I consider when dealing with string manipulation and hash lookups in this problem?

It's important to focus on efficient string transformation (adding one letter) and leveraging hash tables for fast lookups to minimize time complexity.

terminal

Solution

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.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        s = {sum(1 << (ord(c) - 97) for c in w) for w in startWords}
        ans = 0
        for w in targetWords:
            x = sum(1 << (ord(c) - 97) for c in w)
            for c in w:
                if x ^ (1 << (ord(c) - 97)) in s:
                    ans += 1
                    break
        return ans

Continue Practicing

#1684 count the number of consistent strings #1604 alert using same key card three or more times in a one hour period #1418 display table of food orders in a restaurant