Интуиция
Интуиция, лежащая в основе этого решения, заключается в использовании динамического программирования для проверки возможности построения слова путем объединения других слов в наборе.
Подход
Во-первых, входной список слов преобразуется в unordered_set, который является эффективной структурой данных для проверки наличия слова в наборе за постоянное время. Затем создается пустой вектор res для хранения найденных объединенных слов.
Затем код перебирает входной список слов. Для каждого слова создается вектор dp размера n+1, где n — длина слова. Этот вектор используется для хранения возможности построения слова до определенного индекса путем объединения других слов в наборе. Вектор изначально установлен в 0 для всех индексов, кроме первого элемента, который установлен в 1.
Затем код снова перебирает слово и для каждого индекса i проверяет, равно ли значение dp по индексу i 1, что означает возможность построения слова до этого индекса путем объединения других слов. Если да, то проверяется, есть ли в наборе слово, начинающееся с этого индекса и имеющее длину j — i, где j — следующий индекс. Если такое слово найдено, оно обновляет значение dp по индексу j до 1.
Наконец, после итерации по слову код проверяет, равно ли значение dp в последнем индексе 1, что означает, что слово может быть построено конкатенацией других слов в наборе. Если это так, он добавляет слово к результирующему вектору.
После перебора всех слов код возвращает результирующий вектор, содержащий все конкатенированные слова во входном списке слов.
📍 Вот пример того, как код будет работать для слова «кошачья собака» и набора слов {«кошка», «собака»}:
- Во-первых, входной список слов преобразуется в unordered_set, который является эффективной структурой данных для проверки наличия слова в наборе за постоянное время.
- Затем создается пустой вектор res для хранения найденных объединенных слов.
- Затем код перебирает входной список слов. Для каждого слова «кошачья собака» создается вектор dp размера n+1, где n — длина слова. Этот вектор используется для хранения возможности построения слова до определенного индекса путем объединения других слов в наборе. Вектор изначально установлен в 0 для всех индексов, кроме первого элемента, который установлен в 1.
dp = [1, 0, 0, 0, 0, 0, 0]
- Затем код снова перебирает слово и для каждого индекса 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
- Наконец, после итерации по слову код проверяет, равно ли значение 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; } };