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


कठिनाई स्तर आसान
में अक्सर पूछा Facebook
तार

समस्या की जाँच करें यदि दो स्ट्रिंग ऐरे समतुल्य लेटकोड सॉल्यूशन हमें दो प्रदान करता है सरणियों तार के। फिर हमें यह जांचने के लिए कहा जाता है कि क्या ये दो स्ट्रिंग सरणियाँ बराबर हैं। यहाँ तुल्यता का तात्पर्य इस तथ्य से है कि यदि सरणियों में तारों को समतल किया जाता है। फिर समाधि के बाद, दोनों तार समान या समान होंगे। तो समाधान में गहरी गोता लगाने से पहले, आइए पहले कुछ उदाहरणों पर एक नज़र डालते हैं।

उदाहरण

word1[] = {"ab", "c"}
word2[] = {"a", "bc"}
true

स्पष्टीकरण: दोनों सरणियाँ "एबीसी" बनाती हैं यदि हम सभी तारों को समेटते हैं। तो, वे बराबर हैं।

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

जांच के लिए दृष्टिकोण यदि दो स्ट्रिंग एरेज़ समतुल्य लेटकोड समाधान हैं

समस्या ने हमें स्ट्रिंग्स के दो ऐरे दिए। दोनों में से किसी एक में अधिक तार हो सकते हैं। लेकिन जब निष्कर्ष निकाला जाता है, दोनों परिणामी तार समान होंगे। अगर वे वही होते हैं तो हम वापस लौट आते हैं और हम झूठे हो जाते हैं।
अब, समाधान को लागू करने के लिए एक सरल और आसान है प्रत्येक सरणियों में सभी तारों पर बस पार करना है। ट्रेसिंग करते समय, हम स्ट्रिंग्स को समेटते हैं और दो परिणामी स्ट्रिंग्स बनाते हैं। इसलिए, इस संगोष्ठी के संचालन के बाद, हम जांचेंगे कि क्या तार समान हैं। लेकिन इस ऑपरेशन के लिए हमें स्ट्रिंग्स बनाने की आवश्यकता है। इस प्रकार प्रक्रिया को अतिरिक्त स्थान की आवश्यकता होती है। लेकिन हम उस जगह में भी समस्या को हल कर सकते हैं जो अतिरिक्त स्थान का उपयोग किए बिना है।
हम चार चर का उपयोग करेंगे, प्रत्येक सरणी के लिए दो। ये चर सरणी में सूचकांक के रूप में कार्य करेंगे और फिर स्ट्रिंग के लिए सूचकांक होंगे। इस तरह उनमें से दो हमें बताएंगे कि वे पहली सरणी में i1th स्ट्रिंग के j1 वें चरित्र पर हैं। इसी तरह, i2th स्ट्रिंग के j2th चरित्र को i2 और j2 द्वारा दर्शाया गया है। अब जो कुछ बचा है वह है कार्यान्वयन।
हम थोड़ी देर के लूप का उपयोग करते हैं जिसके अंदर हम कुछ शर्तों की जांच करते हैं। यदि दोनों सरणियों में वर्तमान वर्ण मेल नहीं खाते हैं तो हम झूठे लौटते हैं। यदि हम स्ट्रिंग के अंतिम वर्ण पर हैं तो हम जाँच करते हैं। अगर ऐसा होता है तो हम स्ट्रिंग (i) के लिए उपयोग किए जाने वाले सूचकांक को बढ़ाते हैं और वर्ण सूचकांक (j) को 0. पर सेट करते हैं, अन्यथा, बस वेतन वृद्धि j। अंत में, यदि दोनों सरणियों को एक साथ समाप्त किया जाता है, तो हम सही हैं, अन्यथा झूठे।

कोड

चेक ++ के लिए C ++ कोड यदि दो स्ट्रिंग एरर समतुल्य लेटकोड सॉल्यूशन हैं

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

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
    int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
    while(true){
        if(word1[i1][j1] != word2[i2][j2]) return false;
        if(j1 == word1[i1].size()-1)i1++, j1 = 0;
        else j1++;
        if(j2 == word2[i2].size()-1)i2++, j2 = 0;
        else j2++;
        if(i1 == word1.size() && i2 == word2.size())
            return true;
        else if(i1 == word1.size() || i2 == word2.size())
            return false;
    }
}

int main() {
  vector<string> word1 = {"ab", "c"};
  vector<string> word2 = {"a", "bc"};
  cout<<(arrayStringsAreEqual(word1, word2) ? "true" : "false");
  return 0;
}
true

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

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        int i1 = 0, j1 = 0, i2 = 0, j2 = 0;
        while(true){
            if(word1[i1].charAt(j1) != word2[i2].charAt(j2)) return false;
            if(j1 == word1[i1].length()-1){i1++; j1 = 0;}
            else j1++;
            if(j2 == word2[i2].length()-1){i2++; j2 = 0;}
            else j2++;
            if(i1 == word1.length && i2 == word2.length)
                return true;
            else if(i1 == word1.length || i2 == word2.length)
                return false;
        }
    }

  public static void main (String[] args) throws java.lang.Exception
  {
    String[] word1 = {"ab", "c"};
    String[] word2 = {"a", "bc"};
    System.out.print((arrayStringsAreEqual(word1, word2) ? "true" : "false"));
    return 0;
  }
}
true

जटिलता विश्लेषण

समय जटिलता

ओ (मिनट (एन, एम)), क्योंकि हम छोटे स्ट्रिंग के प्रत्येक चरित्र से गुजरते हैं। यहां एन और एम क्रमशः पहले और दूसरे सरणी में वर्णों की संख्या का प्रतिनिधित्व करते हैं।

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

O (1), क्योंकि हमने निरंतर संख्या में चर का उपयोग किया है।