Dota netukša secība s un vārdnīcu dikti[] satur sarakstu ar vārdiem, kas nav tukši, uzdevums ir atgriezties viss iespējamais veidi, kā lauzt teikumu individuāls vārdnīcas vārdi.
Piezīme: To pašu vārdu vārdnīcā var izmantot atkārtoti vairākas reizes, laužot.
Piemēri:
iterēt karti java
Ievade: s = catsanddog dict = [kaķu kaķi un smilšu suns]
Izvade:
kaķi un suns
kaķis smilšu suns
Paskaidrojums: Virkne ir sadalīta 2 veidos, katrā no tiem ir derīgi vārdnīcas vārdi.
Ievade: s = pineapplepenapple dict = [ābolu pildspalva applepen pineapple]
Izvade:
priežu ābols pildspalva ābols
ananāsu pildspalva ābols
priežu ābols ābols
Paskaidrojums: Virkne ir sadalīta 3 veidos, katrā no tiem ir derīgi vārdnīcas vārdi.
Pieeja:
Rekursīvajai pieejai ir divi gadījumi katrā solī (virknes izmērs samazinās katrā solī):
- Iekļaut pašreizējā apakšvirkne risinājumā Ja apakšvirkne pastāv vārdnīcā rekursīvi pārbaudiet pārējo virkni, sākot no nākamā indeksa.
- Izlaist uz pašreizējā apakšvirkne un pārejiet uz nākamo iespējamo apakšvirkni, sākot no tā paša indeksa.
wordBreak(sstart) = wordBreak(s end) if s[sākums:beigas] ∈ vārdnīca
Pamatreģistrs : wordBreak(s start) = patiess tas nozīmē, ka dotajai ievades virknei ir izveidots derīgs teikums.
Iepriekš minētās idejas īstenošanas soļi:
- Konvertēt vārdnīca uz a hash komplekts ātrai meklēšanai.
- Ja sākuma indekss sasniedz garums no virknes(-ēm) tas apzīmē a derīgs spriedums ir uzbūvēts. Pievienot pašreizējo teikumu (curr) uz rezultātu.
- Izvelciet cauri katru apakšvirkne sākot no plkst sākums un beidzas plkst visas iespējamās pozīcijas (beigas).
- Katrai apakšvirknei pārbaudiet, vai tā pastāv vārdnīcā (dictSet).
- Ja derīgs :
- Pievienot vārds pašreizējam teikumam (curr).
- Rekursīvi zvanīt funkcija atlikušo daļu no virknes (no beigām).
- Pēc rekursīvā zvana atgriežas atjaunot stāvoklis curr lai nodrošinātu, ka nākamā izpētes daļa sākas ar pareizs teikums.
// C++ implementation to find valid word // break using Recursion #include
// 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 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 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); });
Izvade
i like sam sung mobile i like samsung mobile
Laika sarežģītība: O((2^n) * k) virknei ar garumu n ir 2^n iespējamie nodalījumi, un katra apakšvirknes pārbaude aizņem O(k) laiku (vidējais apakšvirknes garums k), kas noved pie O((2^n) * k).
Palīgtelpa: O(n) rekursijas steka dēļ sliktākajā gadījumā var nokļūt līdz O(n).