ওয়ার্ড ব্রেক সমস্যা

এই সমস্যায় ইনপুট হিসেবে একটি বাক্য দেওয়া থাকে স্পেস ছাড়া, আর একটি ডিকশনারি দেওয়া থাকে কিছু বৈধ ইংরেজি শব্দের। আমাদের বাক্যটিকে ডিকশনারির শব্দগুলো দিয়ে আলাদা করার সম্ভাব্য সব উপায় বের করতে হবে।

আমরা স্ট্রিংয়ের বাম দিক থেকে সার্চ শুরু করব একটি বৈধ শব্দ খুঁজতে, যখন একটি বৈধ শব্দ পাওয়া যায়, তারপর স্ট্রিংয়ের পরবর্তী অংশে শব্দ খুঁজব।

ইনপুট এবং আউটপুট

ইনপুট: ডিকশনারি হিসেবে বৈধ শব্দের সেট, এবং একটি স্ট্রিং যেখানে শব্দগুলো স্পেস ছাড়া রয়েছে। Dictionary: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream} Given String: "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)

ইনপুট - দেওয়া স্ট্রিং, স্ট্রিংয়ের দৈর্ঘ্য, আলাদা করা স্ট্রিংগুলো।

আউটপুট - ডিকশনারি ব্যবহার করে স্ট্রিং আলাদা করা।

শুরু
  i := 0 থেকে n পর্যন্ত, করুন
    subStr := দেওয়া স্ট্রিংয়ের (0..i) থেকে সাবস্ট্রিং
    যদি subStr ডিকশনারিতে থাকে, তবে
      যদি i = n, তবে
        result := result + subStr
        রেজাল্ট ডিসপ্লে করুন
        রিটার্ন
      wordBreak(সাবস্ট্রিং (i..n-i) থেকে, n-i, result, subStr, 'space')
    শেষ
শেষ

উদাহরণ

#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){ //চেক করুন শব্দটি ডিকশনারিতে আছে কিনা 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); //স্ট্রিংয়ের 0 থেকে i-তম লোকেশন পর্যন্ত স্ট্রিং পান if (isInDict(subStr)) { //যদি subStr ডিকশনারিতে পাওয়া যায় if (i == n) { result += subStr; //রেজাল্টে সাবস্ট্রিং যোগ করুন। cout << result << endl; return; } wordBreak(str.substr(i, n-i), n-i, result + subStr + " "); //অন্যথায় বাকি অংশ ব্রেক করুন } } } 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