140. Word Break II
Дана строка s и словарь строк wordDict. Добавьте пробелы в строку s, чтобы построить предложение, в котором каждое слово является допустимым словом из словаря. Верните все такие возможные предложения в любом порядке.
Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.
Пример:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
C# решение
сопоставлено/оригиналusing System.Collections.Generic;
public class Solution {
public IList<string> WordBreak(string s, IList<string> wordDict) {
HashSet<string> wordSet = new HashSet<string>(wordDict);
List<string> results = new List<string>();
string currentSentence = string.Empty;
Backtrack(s, wordSet, currentSentence, results, 0);
return results;
}
private void Backtrack(string s, HashSet<string> wordSet,
string currentSentence, IList<string> results,
int startIndex) {
if (startIndex == s.Length) {
results.Add(currentSentence);
return;
}
for (int endIndex = startIndex + 1; endIndex <= s.Length; endIndex++) {
string word = s.Substring(startIndex, endIndex - startIndex);
if (wordSet.Contains(word)) {
string originalSentence = currentSentence;
if (!string.IsNullOrEmpty(currentSentence)) currentSentence += " ";
currentSentence += word;
Backtrack(s, wordSet, currentSentence, results, endIndex);
currentSentence = originalSentence;
}
}
}
}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:
public vector<string> WordBreak(string s, vector<string> wordDict) {
HashSet<string> wordSet = new HashSet<string>(wordDict);
List<string> results = new List<string>();
string currentSentence = string.Empty;
Backtrack(s, wordSet, currentSentence, results, 0);
return results;
}
private void Backtrack(string s, HashSet<string> wordSet,
string currentSentence, vector<string> results,
int startIndex) {
if (startIndex == s.size()) {
results.push_back(currentSentence);
return;
}
for (int endIndex = startIndex + 1; endIndex <= s.size(); endIndex++) {
string word = s.Substring(startIndex, endIndex - startIndex);
if (wordSet.Contains(word)) {
string originalSentence = currentSentence;
if (!string.IsNullOrEmpty(currentSentence)) currentSentence += " ";
currentSentence += word;
Backtrack(s, wordSet, currentSentence, results, endIndex);
currentSentence = originalSentence;
}
}
}
}Java решение
сопоставлено/оригиналclass Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
List<String> results = new ArrayList<>();
backtrack(s, wordSet, new StringBuilder(), results, 0);
return results;
}
private void backtrack(
String s,
Set<String> wordSet,
StringBuilder currentSentence,
List<String> results,
int startIndex
) {
if (startIndex == s.length()) {
results.add(currentSentence.toString().trim());
return;
}
for (int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) {
String word = s.substring(startIndex, endIndex);
if (wordSet.contains(word)) {
int currentLength = currentSentence.length();
currentSentence.append(word).append(" ");
backtrack(s, wordSet, currentSentence, results, endIndex);
currentSentence.setLength(currentLength);
}
}
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const results = [];
this._backtrack(s, wordSet, [], results, 0);
return results;
}
_backtrack(s, wordSet, currentSentence, results, startIndex) {
if (startIndex === s.length) {
results.push(currentSentence.join(" "));
return;
}
for (let endIndex = startIndex + 1; endIndex <= s.length; endIndex++) {
const word = s.substring(startIndex, endIndex);
if (wordSet.has(word)) {
currentSentence.push(word);
this._backtrack(s, wordSet, currentSentence, results, endIndex);
currentSentence.pop();
}
}
}
}Python решение
сопоставлено/оригиналclass Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
word_set = set(wordDict)
results = []
self._backtrack(s, word_set, [], results, 0)
return results
def _backtrack(self, s: str, word_set: set, current_sentence: List[str], results: List[str], start_index: int):
if start_index == len(s):
results.append(" ".join(current_sentence))
return
for end_index in range(start_index + 1, len(s) + 1):
word = s[start_index:end_index]
if word in word_set:
current_sentence.append(word)
self._backtrack(s, word_set, current_sentence, results, end_index)
current_sentence.pop()Go решение
сопоставлено/оригиналpackage main
import (
"strings"
)
func wordBreak(s string, wordDict []string) []string {
wordSet := make(map[string]struct{})
for _, word := range wordDict {
wordSet[word] = struct{}{}
}
var results []string
backtrack(s, wordSet, "", &results, 0)
return results
}
func backtrack(s string, wordSet map[string]struct{}, currentSentence string, results *[]string, startIndex int) {
if startIndex == len(s) {
*results = append(*results, currentSentence)
return
}
for endIndex := startIndex + 1; endIndex <= len(s); endIndex++ {
word := s[startIndex:endIndex]
if _, exists := wordSet[word]; exists {
originalSentence := currentSentence
if len(currentSentence) > 0 {
currentSentence += " "
}
currentSentence += word
backtrack(s, wordSet, currentSentence, results, endIndex)
currentSentence = originalSentence
}
}
}
func main() {
s := "leetcode"
wordDict := []string{"leet", "code"}
results := wordBreak(s, wordDict)
for _, result := range results {
println(result)
}
}Algorithm
1️⃣
Инициализация и начальный вызов:
Преобразуйте массив wordDict в множество wordSet для эффективного поиска.
Инициализируйте пустой массив results для хранения допустимых предложений.
Инициализируйте пустую строку currentSentence для отслеживания конструируемого предложения.
Вызовите функцию backtrack с исходной строкой s, множеством wordSet, текущим предложением currentSentence, массивом результатов results и начальным индексом, установленным в 0 — начало входной строки.
Верните results после завершения работы backtrack.
2️⃣
Функция backtrack:
Базовый случай: Если startIndex равен длине строки, добавьте currentSentence в results и вернитесь, так как это означает, что currentSentence представляет собой допустимое предложение.
Итерация по возможным значениям endIndex от startIndex + 1 до конца строки.
3️⃣
Обработка и рекурсия:
Извлеките подстроку word от startIndex до endIndex - 1.
Если word найдено в wordSet:
Сохраните текущее значение currentSentence в originalSentence.
Добавьте word к currentSentence (с пробелом, если это необходимо).
Рекурсивно вызовите backtrack с обновленным currentSentence и endIndex.
Сбросьте currentSentence к его исходному значению (originalSentence) для отката и попробуйте следующий endIndex.
Вернитесь из функции backtrack.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.