वर्ड ब्रेक समस्या

इस समस्या के इनपुट में, स्पेस के बिना एक वाक्य दिया गया है, एक डिक्शनरी भी दी गई है कुछ वैध अंग्रेजी शब्दों की। हमें वाक्य को व्यक्तिगत डिक्शनरी शब्दों में तोड़ने के संभावित तरीके ढूंढने हैं।

हम स्ट्रिंग के बाएं से खोजने का प्रयास करेंगे एक वैध शब्द ढूंढने के लिए, जब एक वैध शब्द मिल जाता है, तो हम उस स्ट्रिंग के अगले भाग में शब्दों की खोज करेंगे।

इनपुट और आउटपुट

इनपुट: डिक्शनरी के रूप में वैध शब्दों का एक सेट, और एक स्ट्रिंग जहां अलग-अलग शब्द बिना स्पेस के रखे गए हैं। डिक्शनरी: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream} दी गई स्ट्रिंग: "ilovemangoicecream" आउटपुट: दी गई स्ट्रिंग को दिए गए शब्दों में तोड़ने के सभी संभावित तरीके। 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  #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