472. Concatenated Words
Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.
Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива.
Пример:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
C# решение
сопоставлено/оригиналusing System;
using System.Collections.Generic;
public class Solution {
private bool Dfs(string word, int length, bool[] visited, HashSet<string> dictionary) {
if (length == word.Length) {
return true;
}
if (visited[length]) {
return false;
}
visited[length] = true;
for (int i = word.Length - (length == 0 ? 1 : 0); i > length; --i) {
if (dictionary.Contains(word.Substring(length, i - length)) &&
Dfs(word, i, visited, dictionary)) {
return true;
}
}
return false;
}
public IList<string> FindAllConcatenatedWordsInADict(string[] words) {
HashSet<string> dictionary = new HashSet<string>(words);
List<string> answer = new List<string>();
foreach (string word in words) {
bool[] visited = new bool[word.Length];
if (Dfs(word, 0, visited, dictionary)) {
answer.Add(word);
}
}
return answer;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private bool Dfs(string word, int length, bool[] visited, HashSet<string> dictionary) {
if (length == word.size()) {
return true;
}
if (visited[length]) {
return false;
}
visited[length] = true;
for (int i = word.size() - (length == 0 ? 1 : 0); i > length; --i) {
if (dictionary.Contains(word.Substring(length, i - length)) &&
Dfs(word, i, visited, dictionary)) {
return true;
}
}
return false;
}
public vector<string> FindAllConcatenatedWordsInADict(vector<string> words) {
HashSet<string> dictionary = new HashSet<string>(words);
List<string> answer = new List<string>();
foreach (string word in words) {
bool[] visited = new bool[word.size()];
if (Dfs(word, 0, visited, dictionary)) {
answer.push_back(word);
}
}
return answer;
}
}Java решение
сопоставлено/оригиналimport java.util.*;
public class Solution {
private boolean dfs(String word, int length, boolean[] visited, Set<String> dictionary) {
if (length == word.length()) {
return true;
}
if (visited[length]) {
return false;
}
visited[length] = true;
for (int i = word.length() - (length == 0 ? 1 : 0); i > length; --i) {
if (dictionary.contains(word.substring(length, i)) && dfs(word, i, visited, dictionary)) {
return true;
}
}
return false;
}
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> dictionary = new HashSet<>(Arrays.asList(words));
List<String> answer = new ArrayList<>();
for (String word : words) {
boolean[] visited = new boolean[word.length()];
if (dfs(word, 0, visited, dictionary)) {
answer.add(word);
}
}
return answer;
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
dfs(word, length, visited, dictionary) {
if (length === word.length) {
return true;
}
if (visited[length]) {
return false;
}
visited[length] = true;
for (let i = word.length - (length === 0 ? 1 : 0); i > length; i--) {
if (dictionary.has(word.slice(length, i)) && this.dfs(word, i, visited, dictionary)) {
return true;
}
}
return false;
}
findAllConcatenatedWordsInADict(words) {
const dictionary = new Set(words);
const answer = [];
for (const word of words) {
const visited = Array(word.length).fill(false);
if (this.dfs(word, 0, visited, dictionary)) {
answer.push(word);
}
}
return answer;
}
}
// Example usage
const solution = new Solution();
const words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
console.log(solution.findAllConcatenatedWordsInADict(words));Python решение
сопоставлено/оригиналclass Solution:
def dfs(self, word, length, visited, dictionary):
if length == len(word):
return True
if visited[length]:
return False
visited[length] = True
for i in range(len(word) - (1 if length == 0 else 0), length, -1):
if word[length:i] in dictionary and self.dfs(word, i, visited, dictionary):
return True
return False
def findAllConcatenatedWordsInADict(self, words):
dictionary = set(words)
answer = []
for word in words:
visited = [False] * len(word)
if self.dfs(word, 0, visited, dictionary):
answer.append(word)
return answerGo решение
сопоставлено/оригиналpackage main
import (
"strings"
)
type Solution struct{}
func (s Solution) dfs(word string, length int, visited []bool, dictionary map[string]bool) bool {
if length == len(word) {
return true
}
if visited[length] {
return false
}
visited[length] = true
for i := len(word) - 1; i > length; i-- {
if dictionary[word[length:i]] && s.dfs(word, i, visited, dictionary) {
return true
}
}
return false
}
func (s Solution) findAllConcatenatedWordsInADict(words []string) []string {
dictionary := make(map[string]bool)
for _, word := range words {
dictionary[word] = true
}
var answer []string
for _, word := range words {
visited := make([]bool, len(word))
if s.dfs(word, 0, visited, dictionary) {
answer = append(answer, word)
}
}
return answer
}
func main() {
solution := Solution{}
words := []string{"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"}
result := solution.findAllConcatenatedWordsInADict(words)
for _, word := range result {
println(word)
}
}Algorithm
Для каждого слова в списке:
Построить неявный граф, в котором узлы представляют индексы символов в слове, а ребра представляют возможность перехода от одного индекса к другому, если подстрока между ними является словом из списка.
Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе.
Если узел word.length достижим от узла 0, добавить слово в ответ.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.