जाँच करें कि क्या एक स्ट्रिंग एक और स्ट्रिंग Leetcode समाधान तोड़ सकता है  


कठिनाई स्तर मध्यम
एल्गोरिदम कोडिंग सहनशीलता लालची साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस छंटाई तार

समस्या का विवरण  

इस समस्या में हमें दो दिए गए हैं तार s1 और s2 एक ही आकार के साथ। जांचें कि क्या स्ट्रिंग s1 का कुछ क्रमचय स्ट्रिंग s2 या इसके विपरीत के कुछ क्रमचय को तोड़ सकता है। दूसरे शब्दों में s2 s1 या इसके विपरीत को तोड़ सकता है।

एक स्ट्रिंग x स्ट्रिंग y (दोनों आकार n) को तोड़ सकता है यदि x [i]> = y [i] (सभी वर्णमाला क्रम में) I और 0 और n-1 के बीच।

उदाहरण

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

स्पष्टीकरण:

"Ayx" s2 = "xya" का एक क्रमपरिवर्तन है जो "abc" को स्ट्रिंग करने के लिए टूट सकता है जो s1 = "abc" का क्रमचय है।

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

स्पष्टीकरण:

S1 = "अबे" के लिए सभी क्रमांकन हैं: "अबे", "एईबी", "बाए", "बीम", "ईईबी" और "ईबा" और एस 2 के लिए सभी क्रमांकन = "एसीडी" हैं: "एसीडी", "एडीसी" "," कैड "," केडीए "," डीएसी "और" डीएएका "। हालाँकि, s1 से कोई भी क्रमपरिवर्तन नहीं है जो s2 और इसके विपरीत से कुछ क्रमचय को तोड़ सकता है।

दृष्टिकोण  

इस समस्या के लिए एक सरल तरीका यह है कि s1 के प्रत्येक क्रमचय के साथ s2 के प्रत्येक क्रमचय की जांच करें ताकि यह पता चल सके कि उनकी कोई जोड़ी मौजूद है जो उपरोक्त स्थिति को पूरा करती है। हम यह काम कर सकते हैं यदि स्ट्रिंग का आकार छोटा है। लेकिन यहां स्ट्रिंग की लंबाई बहुत बड़ी है इसलिए सभी क्रमपरिवर्तन बनाना असंभव है।

यह भी देखें
प्राइम का एल्गोरिथम

समस्या कथन के साथ हम एक स्ट्रिंग को पूरी तरह से दूसरे स्ट्रिंग को कवर करना चाहते हैं। इस अर्थ में कि प्रत्येक वर्ण स्थिति के लिए, एक स्ट्रिंग का वर्ण दूसरी स्ट्रिंग के वर्ण (वर्णमाला क्रम के अनुसार) के बराबर होना चाहिए। यह स्ट्रिंग में सभी वर्णों द्वारा पालन किया जाना चाहिए।
अब यहाँ मुख्य अवलोकन यह है कि यदि हम चाहते हैं कि सभी स्ट्रिंग वर्ण पहले से दूसरे से अधिक हो जाएं तो हमें s1 में छोटे वर्ण की तुलना s2 में छोटे वर्ण से करनी होगी। इसी प्रकार से अधिक से अधिक तत्व। यह क्रमचय जांचने के लिए इष्टतम होगा कि कोई दूसरे को तोड़ता है या नहीं। उदाहरण s1 = "abc" और s2 = "xya"। "Xya" को छाँटने के बाद यह प्रत्येक बिंदु पर "abc" से अधिक होगा।

जाँच करें कि क्या एक स्ट्रिंग एक और स्ट्रिंग Leetcode समाधान तोड़ सकता है

यदि हम सभी वर्णों के लिए s1 को s2 से बड़ा बनाने में सक्षम हैं तो हम सही लौटते हैं। दूसरे मामले में यदि हम s2 को s1 से बड़ा बनाने में सक्षम हैं तो भी हम सही हैं। अन्यथा कोई भी दूसरे को नहीं तोड़ सकता।

कलन विधि:

  • यदि s1 की लंबाई s2 की लंबाई के बराबर नहीं है, तो झूठी लौटें।
  • आरोही या अवरोही क्रम में दोनों स्ट्रिंग को क्रमबद्ध करें।
  • S1 के वर्णों के साथ एक लूप चलाएँ। प्रत्येक वर्ण के लिए जाँच करें यदि s1 [i]> = s2 [i]। यदि सभी पात्र इस शर्त को पूरा करते हैं, तो सही लौटें।
  • अब s2 के अक्षरों के साथ एक लूप चलाएं। प्रत्येक वर्ण के लिए जाँच करें यदि s2 [i]> = s1 [i]। यदि सभी पात्र इस शर्त को पूरा करते हैं, तो सही लौटें।
  • झूठे झूठे।

कार्यान्वयन  

C ++ प्रोग्राम फॉर चेक अगर एक स्ट्रिंग एक और स्ट्रिंग Leetcode Solution को तोड़ सकता है

#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

चेक के लिए जावा प्रोग्राम यदि एक स्ट्रिंग एक और स्ट्रिंग Leetcode समाधान को तोड़ सकता है

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

जाँच के लिए जटिलता विश्लेषण अगर एक स्ट्रिंग एक और स्ट्रिंग Leetcode समाधान तोड़ सकता है  

समय जटिलता

O (nlog (n)): जहाँ n दी गई स्ट्रिंग की लंबाई है। हमने दिए गए स्ट्रिंग को क्रमबद्ध किया और दो बार रैखिक रूप से इसका पता लगाया। इसलिए समय की जटिलता को रोक दिया जाएगा।

यह भी देखें
बेस 7 लेटकोड सॉल्यूशन

अंतरिक्ष जटिलता 

ओ (1): हमने किसी अतिरिक्त मेमोरी का उपयोग नहीं किया। हालांकि कुछ छंटाई वाले एल्गोरिदम के लिए अंतरिक्ष की जटिलता ओ (1) से अधिक हो सकती है।

1