কোনও স্ট্রিং অন্য স্ট্রিং লেটকোড সমাধানটি ভেঙে ফেলতে পারে কিনা তা পরীক্ষা করুন


কাঠিন্য মাত্রা মধ্যম
সহনশীলতা লোভী শ্রেণীবিভাজন স্ট্রিং

সমস্যা বিবৃতি

এই সমস্যায় আমাদের দুটি দেওয়া হয় স্ট্রিং একই আকারের সাথে এস 1 এবং এস 2। স্ট্রিং এস 1 এর কিছু ক্রিয়াকলাপ স্ট্রিং এস 2 বা তদ্বিপরীত এর কিছু ক্রম ছাড়তে পারে কিনা তা পরীক্ষা করুন। অন্য কথায় এস 2 এস 1 বা তদ্বিপরীত ভেঙে ফেলতে পারে।

X [i]> = y [i] (বর্ণানুক্রমিক ক্রমে) 0 এবং n-1 এর মধ্যে সমস্ত i এর জন্য একটি স্ট্রিং এক্স স্ট্রিং y (উভয় আকারের এন) ভাঙ্গতে পারে।

উদাহরণ

s1 = "abc", s2 = "xya"
true

ব্যাখ্যা:

"আইএক্স" হ'ল এস 2 = "xya" এর অনুক্রম যা "abc" স্ট্রিংতে বিভক্ত হতে পারে যা এস 1 = "এবিসি" এর অনুমানযোগ্য।

s1 = "abe", s2 = "acd"
false

ব্যাখ্যা:

এস 1 = "আবে" এর জন্য সমস্ত অনুমতি হ'ল: "আবে", "আবেব", "বিএ", "বিএ", "ইএব" এবং "ইবা" এবং এস 2 = "এসিড" এর জন্য সমস্ত অনুমতি হ'ল: "এসিডি", "অ্যাডিসি" "," ক্যাড "," সিডিএ "," ডাক "এবং" ডিসিএ "। তবে এস 1 থেকে এমন কোনও অনুমতি নেই যা এস 2 এবং তদ্বিপরীত থেকে কিছু ক্রম ছাড়তে পারে।

অভিগমন

এই সমস্যাটির জন্য একটি সহজ পদ্ধতির মধ্যে এস-এর প্রতিটি অনুক্রমের সাথে এস 1 এর প্রতিটি অনুক্রমের পরীক্ষা করা তাদের সন্ধান করতে হবে যে তাদের জুটির উপরের শর্তটি সন্তুষ্ট করে এমন কোনও জোড় আছে কিনা find স্ট্রিংয়ের আকার ছোট হলে আমরা এই জিনিসটি করতে পারি। তবে এখানে স্ট্রিংয়ের দৈর্ঘ্য খুব বড় তাই সমস্ত ক্রমবিকাশ তৈরি করা অসম্ভব।

সমস্যার বিবৃতি সহ আমরা একটি স্ট্রিং দ্বিতীয় স্ট্রিং পুরোপুরি কভার করতে চাই। এই অর্থে আচ্ছাদিত করে যে প্রতিটি অক্ষরের অবস্থানের জন্য, একটি স্ট্রিংয়ের অক্ষরটি দ্বিতীয় স্ট্রিংয়ের (বর্ণানুক্রমিক ক্রম অনুসারে) সমান বর্ণের চেয়ে বড় হওয়া উচিত। এটি স্ট্রিংয়ের সমস্ত অক্ষর অনুসরণ করা উচিত।
এখন এখানে মূল পর্যবেক্ষণটি হ'ল যদি আমরা চাই যে সমস্ত স্ট্রিং অক্ষর দ্বিতীয় স্ট্রিংয়ের চেয়ে প্রথম স্ট্রিংয়ের চেয়ে বড় হয় তবে আমাদের s1 এর ছোট অক্ষরের সাথে এস 2 এর ছোট অক্ষরের সাথে তুলনা করতে হবে। বৃহত্তর এক সঙ্গে একইভাবে বৃহত্তর উপাদান। এই ফলশ্রুতিটি অন্যটি ব্রেক করে কিনা তা পরীক্ষা করার জন্য সর্বোত্তম হবে। S1 = "abc" এবং s2 = "xya" উদাহরণ। "Xya" বাছাই করার পরে এটি প্রতিটি বিন্দুতে "abc" এর চেয়ে বেশি হবে।

কোনও স্ট্রিং অন্য স্ট্রিং লেটকোড সমাধানটি ভেঙে ফেলতে পারে কিনা তা পরীক্ষা করুন

আমরা যদি সমস্ত অক্ষরের জন্য এস 1 এর চেয়ে বেশি এস 2 তৈরি করতে সক্ষম হই তবে আমরা সত্যটিতে ফিরে আসি। দ্বিতীয় ক্ষেত্রে যদি আমরা এস 2 এর চেয়ে বেশি এস 1 তৈরি করতে সক্ষম হয় তবে আমরা সত্যও ফিরে আসি। অন্যথায় কেউ অন্যকে ভাঙতে পারে না।

অ্যালগরিদম:

  • যদি এস 1 এর দৈর্ঘ্য এস 2 এর দৈর্ঘ্যের সমান না হয় তবে মিথ্যা প্রত্যাবর্তন করুন।
  • উভয় স্ট্রিংকে আরোহণ বা অবতরণ ক্রমে সাজান।
  • এস 1 এর অক্ষরগুলি সহ একটি লুপ চালান। S1 [i]> = s2 [i] প্রতিটি অক্ষর পরীক্ষা করে দেখুন। সমস্ত অক্ষর যদি এই শর্তটি পূরণ করে তবে সত্যে ফিরে আসুন।
  • এখন s2 এর অক্ষর বরাবর একটি লুপ চালান। S2 [i]> = s1 [i] প্রতিটি অক্ষর পরীক্ষা করে দেখুন। সমস্ত অক্ষর যদি এই শর্তটি পূরণ করে তবে সত্যে ফিরে আসুন।
  • অন্যথায় মিথ্যা প্রত্যাবর্তন।

বাস্তবায়ন

সি ++ প্রোগ্রাম পরীক্ষা করার জন্য যদি কোনও স্ট্রিং অন্য স্ট্রিং লেটকোড সমাধানটি ভেঙে দিতে পারে

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

bool checkIfCanBreak(string s1, string s2)
{
    if(s1.length() != s2.length()) return false;

    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());

    int i=0;
    while(s1[i])
    {
        if(s1[i]<s2[i]) break;
        i++;
    }

    if(i==s1.length()) return true;

    i=0;
    while(s2[i])
    {
        if(s1[i]>s2[i]) break;
        i++;
    }

    if(i==s2.length()) return true;

    return false;
}

int main() 
{
    string s1 = "abc";
    string s2 = "xya";
    if( checkIfCanBreak( s1, s2) )
        cout<< "true" ;
    else
        cout<< "false";
    return 0; 
}
true

জাভা প্রোগ্রাম চেক করার জন্য যদি কোনও স্ট্রিং অন্য স্ট্রিং লেটকোড সমাধানটি ভেঙে ফেলতে পারে

import java.util.*;
class Rextester{
    
    public static boolean checkIfCanBreak(String s1, String s2) 
    {    
        if(s1.length() != s2.length()) return false;
        
        char[] c1=s1.toCharArray();
        char[] c2=s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        
        int i=0;
        while(i<s1.length())
        {
            if(c1[i]<c2[i]) break;
            i++;
        }
        
        if(i==s1.length()) return true;
        
        i=0;
        while(i<s2.length())
        {
            if(c1[i]>c2[i]) break;
            i++;
        }
        
        if(i==s2.length()) return true;
        
        return false;        
    }
    
    public static void main(String args[])
    {
        String s1 = "abc";
        String s2 = "xya";
        System.out.println(checkIfCanBreak( s1, s2) );
    }
}
true

কোনও স্ট্রিং অন্য স্ট্রিং লেটকোড সমাধানটি ভেঙে দিতে পারে কিনা তা পরীক্ষা করার জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এনলগ (এন)): যেখানে n প্রদত্ত স্ট্রিংয়ের দৈর্ঘ্য। আমরা প্রদত্ত স্ট্রিংটিকে বাছাই করেছি এবং এটিকে দুইবার রৈখিকভাবে ট্র্যাভার করেছি। অতএব সময় জটিলতা অবহেলা করা হবে।

স্পেস জটিলতা ity 

ও (1): আমরা কোনও অতিরিক্ত মেমরি ব্যবহার করি নি। যদিও কিছু বাছাই অ্যালগরিদমের জন্য স্পেস জটিলতা ও (1) এর চেয়ে বেশি হতে পারে।