Untitled

import java.util.*;

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        Map<Integer, Boolean> memo = new HashMap<>();
        List<String> result = new ArrayList<>();

        for (String word : words) {
            if (isConcatenated(word, 0, wordSet, memo)) {
                result.add(word);
            }
        }
        return result;
    }

    private boolean isConcatenated(String word, int index, Set<String> wordSet, Map<Integer, Boolean> memo) {
        // Base case: if we've processed the entire word
        if (index == word.length()) return true;

        // Check if result is already memoized for the current index
        if (memo.containsKey(index)) return memo.get(index);

        for (int end = index + 1; end <= word.length(); end++) {
            String prefix = word.substring(index, end);

            // If the prefix exists in the set and the suffix can be recursively processed
            if (wordSet.contains(prefix) && (end != word.length() || isConcatenated(word, end, wordSet, memo))) {
                memo.put(index, true);
                return true;
            }
        }

        // Mark as false if no valid segmentation found
        memo.put(index, false);
        return false;
    }
}