Practice/Meta/Find Words That Contain Other Words as Substrings

Find Words That Contain Other Words as Substrings

AI-Enabled CodingMust

Problem

You are given an array of strings where each string represents a word. Your task is to identify and return all words that contain at least one other word from the array as a substring. A word cannot be considered as containing itself.

Return the result in the same order as the words appear in the input array. If a word appears multiple times and qualifies as a container word, include all occurrences in the result.

Requirements

1. Return all words that contain at least one other distinct word from the list as a substring
2. A word should not be considered as containing itself (even if it appears multiple times in the array)
3. Preserve the original order of words from the input array
4. If there are duplicate words that qualify, include all occurrences in the result
5. Return an empty array if no words qualify

Constraints

• 0 ≤ words.length ≤ 1000
• 1 ≤ words[i].length ≤ 100
• All words consist of lowercase English letters only
• Time complexity should be reasonable for the given constraints
• Words are case-sensitive

Examples

Example 1:

Input: words = ['apple', 'app', 'banana', 'nana'] Output: ['apple', 'banana'] Explanation: 'apple' contains 'app' as a substring, and 'banana' contains 'nana' as a substring.

Example 2:

Input: words = ['cat', 'dog', 'bird'] Output: [] Explanation: None of these words contain any other word from the list as a substring.

Example 3:

Input: words = ['test', 'testing', 'tester', 'es'] Output: ['testing', 'tester'] Explanation: 'testing' contains 'test' and 'es'. 'tester' contains 'test' and 'es'. Both are container words.

Example 4:

Input: words = ['abc', 'ab', 'abc', 'c'] Output: ['abc', 'abc'] Explanation: Both instances of 'abc' contain 'ab' and 'c', so both occurrences are returned.