LeetCode 472: Concatenated Words Solution

Master LeetCode problem 472 (Concatenated Words), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

472. Concatenated Words

Hard

Array String Dynamic Programming Depth-First Search Trie

Problem Explanation

Explanation

To solve this problem, we can use a dynamic programming approach. We first create a set of all words to efficiently check if a word can be broken into smaller words. Then, we iterate through each word in the input list and check if it can be created by concatenating smaller words from the set. We use a dynamic programming array to store whether a substring can be formed by concatenating smaller words. Finally, we return the list of concatenated words.

Algorithm:
1. Create a set of all words for efficient lookup.
2. Sort the input list by length to optimize word concatenation checks.
3. Initialize a dynamic programming array to store if a substring can be formed by concatenating smaller words.
4. Iterate through each word in the input list and check if it can be formed by concatenating smaller words.
5. Update the dynamic programming array accordingly.
6. Return the list of concatenated words.
Time Complexity: O(n * m^2) where n is the number of words and m is the average length of words.
Space Complexity: O(n) for storing the set of words and dynamic programming array.

Solution Code

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> result = new ArrayList<>();
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        
        for (String word : words) {
            if (word.isEmpty()) continue;
            int n = word.length();
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;
            
            for (int i = 0; i < n; i++) {
                if (!dp[i]) continue;
                
                for (int j = i + 1; j <= n; j++) {
                    if (j - i < n && wordSet.contains(word.substring(i, j))) {
                        dp[j] = true;
                    }
                }
                
                if (dp[n]) {
                    result.add(word);
                    break;
                }
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 472 (Concatenated Words)?

This page provides optimized solutions for LeetCode problem 472 (Concatenated Words) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 472 (Concatenated Words)?

The time complexity for LeetCode 472 (Concatenated Words) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 472 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 472 in Java, C++, or Python.

Back to LeetCode Solutions