Concatenated Words

class Solution {
    bool searchSubset(const string& target, int idx, vector<bool>& seen,
                      const unordered_set<string>& dict) {
        if (idx == target.length()) return true;
        if (seen[idx]) return false;
        seen[idx] = true;
        for (int end = target.length() - (idx == 0 ? 1 : 0); end > idx; --end) {
            if (dict.count(target.substr(idx, end - idx)) &&
                searchSubset(target, end, seen, dict)) {
                return true;
            }
        }
        return false;
    }

public:
    vector<string> findConcatWords(vector<string>& wordsList) {
        unordered_set<string> dict(wordsList.begin(), wordsList.end());
        vector<string> concatenatedWords;
        for (const string& word : wordsList) {
            vector<bool> visited(word.size(), false);
            if (searchSubset(word, 0, visited, dict)) {
                concatenatedWords.push_back(word);
            }
        }
        return concatenatedWords;
    }
};

The given C++ code is a solution for finding all concatenated words in a list. The core function implements a recursive strategy with memoization to check if a word can be formed by concatenating other words from the list. Here's a breakdown of how this code works:

• The function searchSubset checks if a substring of the target word can be found in a dictionary of words (dict). It uses a boolean vector seen to avoid reprocessing the same index in the target word, enhancing efficiency via memoization.

• For each position in the word (idx), the function iterates backwards to try and find a valid word in the dictionary that ends at the current position. If such a word is found, it recursively checks the rest of the substring starting from the end of this word.

• The function findConcatWords initializes a hash set (dict) with all the words from the input list for quick look-up. It then iterates over each word to see if it can be constructed from other words in the list using searchSubset.

• If searchSubset returns true for a word, implying that the word can indeed be formed by concatenating other words from the list (excluding itself in recursion), then this word is added to the result list concatenatedWords.

Implement these functions for efficiently detecting and listing concatenated words in any given list of words. This solution makes use of both recursion for splitting the words and memoization to store already visited substrings, optimizing the process significantly.

class Solution {
    private boolean searchSubstring(final String str, int pos, final boolean[] mark, final Set<String> wordSet) {
        if (pos == str.length()) {
            return true;
        }
        if (mark[pos]) {
            return false;
        }
        mark[pos] = true;
        for (int i = str.length() - (pos == 0 ? 1 : 0); i > pos; --i) {
            if (wordSet.contains(str.substring(pos, i)) && searchSubstring(str, i, mark, wordSet)) {
                return true;
            }
            
        }
        return false;
    }
    
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        final Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        final List<String> result = new ArrayList<>();
        for (final String str : words) {
            final int len = str.length();
            final boolean[] mark = new boolean[len];
            if (searchSubstring(str, 0, mark, wordSet)) {
                result.add(str);
            }
        }
        return result;   
    }
}

In the Java program titled "Concatenated Words", the task is to identify words in a given dictionary that are formed by concatenating other words from the same dictionary. Here's a breakdown of how the solution accomplishes this:

• A private helper method searchSubstring is used, which leverages recursion to determine if a substring can be formed by concatenating other words in the dictionary. This method utilizes dynamic programming by marking positions in the word using a boolean array to avoid redundant checks and hence optimize the process.

• The core of the findAllConcatenatedWordsInADict function involves:

  • Creating a HashSet to store the words for quick lookup.
  • Iterating through each word and using the searchSubstring method to determine if that word is a concatenated word. The iteration skips directly re-identifying a word as a concatenation of itself to enhance efficiency.
  • Each valid concatenated word is collected into a List<String> which is eventually returned.

The algorithm efficiently checks each word by breaking it down into possible substrings and recursing deeper only if those substrings are found in the dictionary. This prevents unnecessary computations and speeds up the process of identifying concatenated words.