비어 있지 않은 시퀀스가 주어지면 에스 그리고 사전 사전[] 작업이 반환할 비어 있지 않은 단어 목록이 포함되어 있음 모두 가능 문장을 끊는 방법 개인 사전 단어.
메모: 사전에 있는 동일한 단어를 재사용할 수 있음 다수의 깨지는 동안 시간.
예:
입력: s = catsanddog dict = [고양이 고양이와 모래 개]
산출:
고양이와 개
고양이 모래 개
설명: 문자열은 위의 두 가지 방식으로 분할되며 각 방식은 모두 유효한 사전 단어입니다.
입력: s = 파인애플펜애플 dict = [애플 펜 애플펜 파인 파인애플]
산출:
소나무 사과 펜 사과
파인애플 펜 사과
소나무 사과펜 사과
설명: 문자열은 위의 3가지 방식으로 분할되며 각 방식은 모두 유효한 사전 단어입니다.
접근하다:
피트 데이비슨 나이
재귀적 접근 방식에는 다음이 있습니다. 두 가지 경우 각 단계에서 (문자열의 크기 감소하다 각 단계에서):
- 포함하다 솔루션의 현재 하위 문자열 하위 문자열이 사전에 존재하는 경우 재귀적으로 다음 인덱스부터 시작하여 나머지 문자열을 확인하십시오.
- 건너뛰다 그만큼 현재 하위 문자열 동일한 인덱스에서 시작하여 가능한 다음 하위 문자열로 이동합니다.
wordBreak(sstart) = wordBreak(s end) if s[start:end] ∈ 사전
기본 사례: wordBreak(s start) = true 이는 주어진 입력 문자열에 대해 유효한 문장이 구성되었음을 의미합니다.nfa에서 dfa로
위의 아이디어를 구현하는 단계:
- 변환하다 사전 으로 해시 세트 빠른 검색을 위해.
- 만약 인덱스 시작 에 도달 길이 문자열 중 이는 다음을 의미합니다. 유효한 문장 건설되었습니다. 추가하다 현재 문장(curr)을 결과로 보냅니다.
- 루프스루 모든 하위 문자열 에서 시작 시작 그리고 종결 ~에 가능한 모든 위치(끝).
- 각 하위 문자열에 대해 다음과 같은지 확인합니다. 존재한다 사전에 (dictSet).
- 유효한 경우 :
- 추가 현재 문장의 단어(curr).
- 재귀적으로 호출 에 대한 기능 남은 부분 문자열의 (끝부터).
- 재귀 호출이 반환된 후 복원하다 상태 현재 탐사의 다음 분기가 올바른 문장.
// 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); });
산출
i like sam sung mobile i like samsung mobile
시간 복잡도: O((2^n) * k) 길이가 n인 문자열의 경우 2^n개의 가능한 파티션이 있으며 각 하위 문자열 검사에는 O((2^n) * k)에 이르는 O(k) 시간(평균 하위 문자열 길이 k)이 소요됩니다.
보조 공간: O(n) 재귀 스택으로 인해 최악의 경우 O(n)만큼 깊어질 수 있습니다.