Интуиция

Интуиция, лежащая в основе этого решения, заключается в использовании динамического программирования для проверки возможности построения слова путем объединения других слов в наборе.

Подход

Во-первых, входной список слов преобразуется в unordered_set, который является эффективной структурой данных для проверки наличия слова в наборе за постоянное время. Затем создается пустой вектор res для хранения найденных объединенных слов.

Затем код перебирает входной список слов. Для каждого слова создается вектор dp размера n+1, где n — длина слова. Этот вектор используется для хранения возможности построения слова до определенного индекса путем объединения других слов в наборе. Вектор изначально установлен в 0 для всех индексов, кроме первого элемента, который установлен в 1.

Затем код снова перебирает слово и для каждого индекса i проверяет, равно ли значение dp по индексу i 1, что означает возможность построения слова до этого индекса путем объединения других слов. Если да, то проверяется, есть ли в наборе слово, начинающееся с этого индекса и имеющее длину j — i, где j — следующий индекс. Если такое слово найдено, оно обновляет значение dp по индексу j до 1.

Наконец, после итерации по слову код проверяет, равно ли значение dp в последнем индексе 1, что означает, что слово может быть построено конкатенацией других слов в наборе. Если это так, он добавляет слово к результирующему вектору.

После перебора всех слов код возвращает результирующий вектор, содержащий все конкатенированные слова во входном списке слов.

📍 Вот пример того, как код будет работать для слова «кошачья собака» и набора слов {«кошка», «собака»}:

  1. Во-первых, входной список слов преобразуется в unordered_set, который является эффективной структурой данных для проверки наличия слова в наборе за постоянное время.
  2. Затем создается пустой вектор res для хранения найденных объединенных слов.
  3. Затем код перебирает входной список слов. Для каждого слова «кошачья собака» создается вектор dp размера n+1, где n — длина слова. Этот вектор используется для хранения возможности построения слова до определенного индекса путем объединения других слов в наборе. Вектор изначально установлен в 0 для всех индексов, кроме первого элемента, который установлен в 1.

dp = [1, 0, 0, 0, 0, 0, 0]

  1. Затем код снова перебирает слово и для каждого индекса i проверяет, равно ли значение dp по индексу i 1, что означает возможность построения слова до этого индекса путем объединения других слов. Если да, то проверяется, есть ли в наборе слово, начинающееся с этого индекса и имеющее длину j — i, где j — следующий индекс. Если такое слово найдено, оно обновляет значение dp по индексу j до 1.

i = 0, j = 3, check if "cat" is in set: Yes, update dp[3] = 1 i = 3, j = 6, check if "dog" is in set: Yes, update dp[6] = 1

  1. Наконец, после итерации по слову код проверяет, равно ли значение dp в последнем индексе 1, что означает, что слово может быть построено конкатенацией других слов в наборе. Если это так, он добавляет слово к результирующему вектору.

dp = [1, 0, 0, 1, 0, 0, 1]

Поскольку последний индекс массива dp равен 1, это означает, что слово «кошачья собака» может быть создано путем объединения других слов в наборе, поэтому оно добавляется к результирующему вектору.

Таким образом, этот подход проверяет, является ли слово составным словом, разбивая его на подстроки и проверяя, является ли каждая подстрока словом в наборе, используя массив dp для хранения промежуточных результатов. Этот метод намного эффективнее, чем проверка всех возможных конкатенаций слов.

Сложность

  • Временная сложность:
    Временная сложность этого решения составляет O(n * L²), где n — количество слов во входном списке, а L — максимальная длина слов.
    Основным источником временной сложности являются вложенные циклы, которые перебирают слова и символы слов. Внешний цикл перебирает слова и имеет временную сложность O(n). Внутренний цикл перебирает символы слов и имеет временную сложность O(L). Внутренний цикл также выполняет дополнительные операции, такие как проверка наличия слова в наборе и обновление массива dp, что также увеличивает общую временную сложность.
  • Пространственная сложность:
    Пространственная сложность равна O(n * L), где n — количество слов во входном списке, а L — максимальная длина слова. Основным источником пространственной сложности является массив dp, который создается для каждого слова и имеет размер L. Кроме того, создание unordered_set всех слов также занимает O(n) пространства.

Код

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> words_set;
        for (string word : words) words_set.insert(word);
        vector<string> res;
    
        for (string word : words) {
            int n = word.size();
            vector<int> dp(n + 1, 0);
            dp[0] = 1;
            for (int i = 0; i < n; i++) {
                if (!dp[i]) continue;
                for (int j = i + 1; j <= n; j++) {
                    if (j - i < n && words_set.count(word.substr(i, j - i))) {
                        dp[j] = 1;
                    }
                }
                if (dp[n]) {
                    res.push_back(word);
                    break;
                }
            }
        }
        return res;
    }
};