이 문제의 입력에서 한 문장은 공백 없이 제공되며 다른 사전에는 유효한 영어 단어도 제공됩니다. 개별 사전 단어에서 문장을 깰 수 있는 가능한 방법을 찾아야 합니다.
유효한 단어가 발견되면 유효한 단어를 찾기 위해 문자열 왼쪽부터 검색을 시도하고 해당 문자열의 다음 부분에서 단어를 검색합니다.
입력 및 출력
Input: A set of valid words as dictionary, and a string where different words are placed without spaces. Dictionary: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream} Given String: “ilovemangoicecream” Output: All possible ways to break the string into given words. i love man go ice cream i love man go icecream i love mango ice cream i love mango icecream
알고리즘
wordBreak(string, n, result)
입력 - 주어진 문자열, 문자열의 길이, 분리된 문자열.
출력 - 사전을 사용하여 문자열을 분리합니다.
Begin for i := 0 to n, do subStr := substring of given string from (0..i) if subStr is in dictionary, then if i = n, then result := result + subStr display the result return wordBreak(substring from (i..n-i), n-i, result, subStr, ‘space’) done End
예시
#include <iostream> #define N 13 using namespace std; string dictionary[N] = {"mobile","samsung","sam","sung","man","mango", "icecream","and", "go","i","love","ice","cream"}; int isInDict(string word){ //check whether the word is in dictionary or not for (int i = 0; i < N; i++) if (dictionary[i].compare(word) == 0) return true; return false; } void wordBreak(string str, int n, string result) { for (int i=1; i<=n; i++) { string subStr = str.substr(0, i); //get string from 0 to ith location of the string if (isInDict(subStr)) { //if subStr is found in the dictionary if (i == n) { result += subStr; //add substring in the result. cout << result << endl; return; } wordBreak(str.substr(i, n-i), n-i, result + subStr + " "); //otherwise break rest part } } } int main() { string str="iloveicecreamandmango"; wordBreak(str, str.size(),""); }
출력
i love man go ice cream i love man go icecream i love mango ice cream i love mango icecream