バックトラッキングを使用した単語区切りの問題

空ではないシーケンスを指定した場合 s そして辞書 辞書[] タスクが返す空でない単語のリストを含む あらゆる可能性 文を区切る方法個人辞書の言葉。
注記： 辞書にある同じ単語が再利用される可能性がある複数ブレイク中に何度か。
例:

入力： s = catsanddog dict = [猫猫と砂犬]
出力：
猫と犬
猫砂犬
説明： 文字列は上記の 2 つの方法に分割され、いずれも有効な辞書の単語です。

入力： s = パイナップルペンアップル dict = [アップルペン、アッポーペン、パイナップル]
出力：
パインアップルペンアップル
パイナップルペンアップル
パインアップルペンアップル
説明： 文字列は上記の 3 つの方法に分割され、いずれの方法もすべて有効な辞書の単語です。

アプローチ：

再帰的アプローチには、次のものがあります。 2つのケース 各ステップで (文字列のサイズ) 減少する 各ステップで):

含むソリューション内の現在の部分文字列部分文字列が辞書内に存在する場合 再帰的に 次のインデックスから始まる文字列の残りを確認します。
スキップ の 現在の部分文字列 そして、同じインデックスから始まる次の可能な部分文字列に移動します。
wordBreak(sstart) = wordBreak(s end) if s[start:end] ∈ 辞書

基本ケース: wordBreak(s start) = true これは、指定された入力文字列に対して有効な文が構築されたことを意味します。

上記のアイデアを実装する手順は次のとおりです。

変換する辞書にハッシュセット素早い検索のために。
もし 開始インデックス に達する長さ文字列のうち、それが意味するもの 有効な文 が構築されています。追加現在の文 (curr) を結果に返します。
ループスルー毎 部分文字列 から始まる 始める そして エンディング で 可能なすべての位置 (終了)。
各部分文字列について、 存在します 辞書にある (dictSet)。
有効な場合 :
- 追加現在の文に単語を追加します (curr)。
- 再帰的に呼び出す の関数 残りの部分 文字列の(末尾から)。
再帰呼び出しが戻った後 復元する の状態 カレー 次の探索ブランチが確実に開始されるようにするため、 正しい文。

C++

// C++ implementation to find valid word // break using Recursion #include    using namespace std; // Helper function to perform backtracking void wordBreakHelper(string& s unordered_set<string>& dictSet   string& curr vector<string>& res   int start) {  // If start reaches the end of the string  // save the result  if (start == s.length()) {  res.push_back(curr);  return;  }  // Try every possible substring from the current index  for (int end = start + 1; end <= s.length(); ++end) {  string word = s.substr(start end - start);  // Check if the word exists in the dictionary  if (dictSet.count(word)) {  string prev = curr;  // Append the word to the current sentence  if (!curr.empty()) {  curr += ' ';  }  curr += word;  // Recurse for the remaining string  wordBreakHelper(s dictSet curr res end);  // Backtrack to restore the current sentence  curr = prev;  }  } } // Main function to generate all possible sentence breaks vector<string> wordBreak(string s vector<string>& dict) {    // Convert dictionary vector  // to an unordered set  unordered_set<string>  dictSet(dict.begin() dict.end());  vector<string> res;   string curr;   wordBreakHelper(s dictSet curr res 0);  return res;  } int main() {    string s = 'ilikesamsungmobile';  vector<string> dict = {'i' 'like' 'sam' 'sung'  'samsung' 'mobile' 'ice'  'and' 'cream' 'icecream'  'man' 'go' 'mango'};  vector<string> result = wordBreak(s dict);  for (string sentence : result) {  cout << sentence << endl;  }  return 0; }

Java

// Java implementation to find valid  // word break using Recursion import java.util.*; class GfG {  // Helper function to perform backtracking  static void wordBreakHelper(String s HashSet<String> dictSet   String curr List<String> res   int start) {  // If start reaches the end of the string  // save the result  if (start == s.length()) {  res.add(curr);  return;  }  // Try every possible substring from the current index  for (int end = start + 1; end <= s.length(); ++end) {  String word = s.substring(start end);  // Check if the word exists in the dictionary  if (dictSet.contains(word)) {  String prev = curr;  // Append the word to the current sentence  if (!curr.isEmpty()) {  curr += ' ';  }  curr += word;  // Recurse for the remaining string  wordBreakHelper(s dictSet curr res end);  // Backtrack to restore the current sentence  curr = prev;  }  }  }  // Main function to generate all possible sentence breaks  static List<String> wordBreak(String s List<String> dict) {  // Convert dictionary vector to a HashSet  HashSet<String> dictSet = new HashSet<>(dict);  List<String> res = new ArrayList<>();  String curr = '';  wordBreakHelper(s dictSet curr res 0);  return res;  }  public static void main(String[] args) {  String s = 'ilikesamsungmobile';  List<String> dict = Arrays.asList('i' 'like' 'sam' 'sung'  'samsung' 'mobile' 'ice'  'and' 'cream' 'icecream'  'man' 'go' 'mango');  List<String> result = wordBreak(s dict);  for (String sentence : result) {  System.out.println(sentence);  }  } }

Python

# Python implementation to find valid  # word break using Recursion def wordBreakHelper(s dictSet curr res start): # If start reaches the end of the string # save the result if start == len(s): res.append(curr) return # Try every possible substring from the current index for end in range(start + 1 len(s) + 1): word = s[start:end] # Check if the word exists in the dictionary if word in dictSet: prev = curr # Append the word to the current sentence if curr: curr += ' ' curr += word # Recurse for the remaining string wordBreakHelper(s dictSet curr res end) # Backtrack to restore the current sentence curr = prev def wordBreak(s dict): # Convert dictionary list to a set dictSet = set(dict) res = [] curr = '' wordBreakHelper(s dictSet curr res 0) return res if __name__=='__main__': s = 'ilikesamsungmobile' dict = ['i' 'like' 'sam' 'sung' 'samsung' 'mobile' 'ice' 'and' 'cream' 'icecream' 'man' 'go' 'mango'] result = wordBreak(s dict) for sentence in result: print(sentence)

// C# implementation to find valid word  // break using Recursion using System; using System.Collections.Generic; class GfG {    // Helper function to perform backtracking  static void wordBreakHelper(string s HashSet<string> dictSet  ref string curr ref List<string> res  int start) {    // If start reaches the end of the string  // save the result  if (start == s.Length) {  res.Add(curr);  return;  }  // Try every possible substring from the current index  for (int end = start + 1; end <= s.Length; ++end) {    string word = s.Substring(start end - start);  // Check if the word exists in the dictionary  if (dictSet.Contains(word)) {  string prev = curr;  // Append the word to the current sentence  if (curr.Length > 0) {  curr += ' ';  }  curr += word;  // Recurse for the remaining string  wordBreakHelper(s dictSet ref curr   ref res end);  // Backtrack to restore the current sentence  curr = prev;  }  }  }  // Main function to generate all possible sentence breaks  static List<string> wordBreak(string s   List<string> dict) {    // Convert dictionary list to a HashSet  HashSet<string> dictSet   = new HashSet<string>(dict);  List<string> res = new List<string>();  string curr = '';  wordBreakHelper(s dictSet ref curr ref res 0);  return res;  }  static void Main() {    string s = 'ilikesamsungmobile';  List<string> dict  = new List<string> {'i' 'like' 'sam' 'sung'  'samsung' 'mobile' 'ice'  'and' 'cream' 'icecream'  'man' 'go' 'mango'};  List<string> result = wordBreak(s dict);  foreach (string sentence in result) {  Console.WriteLine(sentence);  }  } }

JavaScript

// JavaScript implementation to find valid  // word break using Recursion // Helper function to perform backtracking function wordBreakHelper(s dictSet curr res start) {  // If start reaches the end of the string save the result  if (start === s.length) {  res.push(curr);  return;  }  // Try every possible substring from the current index  for (let end = start + 1; end <= s.length; ++end) {  let word = s.substring(start end);  // Check if the word exists in the dictionary  if (dictSet.has(word)) {  let prev = curr;  // Append the word to the current sentence  if (curr.length > 0) {  curr += ' ';  }  curr += word;  // Recurse for the remaining string  wordBreakHelper(s dictSet curr res end);  // Backtrack to restore the current sentence  curr = prev;  }  } } // Main function to generate all possible sentence breaks function wordBreak(s dict) {  // Convert dictionary array to a Set  let dictSet = new Set(dict);  let res = [];  let curr = '';  wordBreakHelper(s dictSet curr res 0);  return res; } let s = 'ilikesamsungmobile'; let dict = ['i' 'like' 'sam' 'sung'  'samsung' 'mobile' 'ice'  'and' 'cream' 'icecream'  'man' 'go' 'mango']; let result = wordBreak(s dict); result.forEach((sentence) => {  console.log(sentence);  });

出力

i like sam sung mobile i like samsung mobile

時間計算量: O((2^n) * k) 長さ n の文字列の場合、可能な分割は 2^n 個あり、各部分文字列のチェックには O(k) 時間 (平均部分文字列長 k) がかかり、O((2^n) * k) になります。
補助スペース: O(n) 再帰のため、スタックは最悪の場合 O(n) まで深くなる可能性があります。

クイズの作成