C++-এ চা চা স্লাইড: স্ট্রিং রোটেশন যাচাই

দুটি স্ট্রিং s এবং t দেওয়া থাকলে, আমাদের যাচাই করতে হবে s-কে ঘুরিয়ে (rotate) t পাওয়া যায় কিনা।

সমস্যা বিবরণ

উদাহরণস্বরূপ, s = "helloworld" এবং t = "worldhello" হলে, s-কে ঘুরিয়ে t পাওয়া যায়, তাই আউটপুট হবে true।

সমাধানের পদ্ধতি

1. যদি s এবং t-র দৈর্ঘ্য সমান না হয়, তবে false ফেরত দিন।
2. s-কে নিজের সাথে যোগ করুন: s = s + s।
3. নতুন s-র মধ্যে t আছে কিনা তা যাচাই করুন। থাকলে true, নাহলে false।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(string s0, string s1) {
        if (s0.size() != s1.size())
            return false;
        string s = s0 + s0;
        return s.find(s1) != string::npos;
    }
};

int main() {
    Solution ob;
    cout << (ob.solve("helloworld", "worldhello"));
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: "helloworld", "worldhello"

আউটপুট: 1 (true)

অ্যালগরিদম ব্যাখ্যা

এই পদ্ধতিটি কাজ করে কারণ একটি স্ট্রিংকে নিজের সাথে যোগ করলে (s+s), স্ট্রিংটির সকল সম্ভাব্য রোটেশন নতুন স্ট্রিংয়েরsubstring হিসেবে উপস্থিত থাকে। find() ফাংশনটি O(n) সময়ে সাবস্ট্রিং খুঁজে বের করে।