ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಹೊಂದಾಣಿಕೆ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್
ಸ್ಟ್ರಿಂಗ್

ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಹೊಂದಾಣಿಕೆಯ ಸಮಸ್ಯೆ ನಮಗೆ ತಂತಿಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಒದಗಿಸುತ್ತದೆ. ಸಮಸ್ಯೆ ನಮ್ಮನ್ನು ಬೇರೆಯವರ ತಲಾಧಾರಗಳಾಗಿರುವ ತಂತಿಗಳನ್ನು ಹುಡುಕಲು ಕೇಳುತ್ತದೆ ಸ್ಟ್ರಿಂಗ್ ಇನ್ಪುಟ್ನಿಂದ. ತ್ವರಿತ ಜ್ಞಾಪನೆ, ಸಬ್‌ಸ್ಟ್ರಿಂಗ್ ಎಂಬುದು ಎರಡೂ ತುದಿಗಳಿಂದ ಅಕ್ಷರಗಳನ್ನು ತೆಗೆದುಹಾಕಿದ ನಂತರ ಉಳಿದಿರುವ ಸ್ಟ್ರಿಂಗ್‌ನ ಒಂದು ಭಾಗವಲ್ಲ. ನೀವು ಎರಡೂ ತುದಿಗಳಿಂದ 0 ಅಕ್ಷರಗಳನ್ನು ಸಹ ತೆಗೆದುಹಾಕಬಹುದು. ಮತ್ತು ತೆಗೆದುಹಾಕಲಾದ ಅಕ್ಷರಗಳ ಸಂಖ್ಯೆ ಒಂದೇ ಆಗಿರಬೇಕಾಗಿಲ್ಲ. ಆದ್ದರಿಂದ, ಉತ್ತಮ ತಿಳುವಳಿಕೆಗಾಗಿ ನಾವು ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ನೋಡೋಣ.

ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಹೊಂದಾಣಿಕೆ

words = ["mass","as","hero","superhero"]
["as","hero"]

ವಿವರಣೆ: mass ಟ್‌ಪುಟ್ “as” ಅನ್ನು ಹೊಂದಿದೆ ಏಕೆಂದರೆ ಅದು “ದ್ರವ್ಯರಾಶಿ” ಯಲ್ಲಿ ಬರುತ್ತದೆ. ಅಂತೆಯೇ, “ಹೀರೋ” “ಸೂಪರ್ ಹೀರೋ” ನ ಒಂದು ಭಾಗವಾಗಿದೆ. ಹೀಗಾಗಿ, ಇನ್‌ಪುಟ್‌ಗಳ ಸಬ್‌ಸ್ಟ್ರಿಂಗ್‌ಗಳನ್ನು ನಾವು ಸರಳವಾಗಿ ಕಂಡುಕೊಂಡಿದ್ದೇವೆ.

words = ["leetcode","et","code"]
["et","code"]

ವಿವರಣೆ: ಸಬ್‌ಸ್ಟ್ರಿಂಗ್‌ಗಳು ಒಂದೇ ಸ್ಟ್ರಿಂಗ್‌ನಿಂದ ಆಗಿರಬಹುದು ಎಂದು ಈ ಉದಾಹರಣೆಯು ತೋರಿಸುತ್ತದೆ. ಇಲ್ಲಿರುವಂತೆ, output ಟ್‌ಪುಟ್‌ನಲ್ಲಿರುವ ಎರಡೂ ತಂತಿಗಳು “ಲೀಟ್‌ಕೋಡ್” ನ ತಲಾಧಾರವಾಗಿದೆ.

ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಹೊಂದಾಣಿಕೆಗಾಗಿ ಅನುಸಂಧಾನ

ನಿರ್ದಿಷ್ಟ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುವ ಇನ್‌ಪುಟ್‌ನಿಂದ ತಂತಿಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳಲು ಸಮಸ್ಯೆ ನಮ್ಮನ್ನು ಕೇಳಿದೆ. ಷರತ್ತು ಎಂದರೆ ಸ್ಟ್ರಿಂಗ್ ಸ್ಟ್ರಿಂಗ್‌ನ ಸಬ್‌ಸ್ಟ್ರಿಂಗ್ ಆಗಿರಬೇಕು ಅದು ಇನ್ಪುಟ್‌ನಲ್ಲಿದೆ. ಆದ್ದರಿಂದ, ನಾವು ಕೆಲವು ಇತರ ಸ್ಟ್ರಿಂಗ್‌ಗಳ ತಲಾಧಾರವಾಗಿರುವ ತಂತಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಅನುಕರಿಸಲು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಉಳಿದಿರುವ ಏಕೈಕ ತೊಡಕು ಅನುಷ್ಠಾನ. ಆದ್ದರಿಂದ, ನಮ್ಮ .ಟ್‌ಪುಟ್‌ನಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ತಂತಿಗಳ ಜಾಡು ಹಿಡಿಯಲು ನಾವು ಹ್ಯಾಶ್‌ಸೆಟ್ ಅಥವಾ ಕ್ರಮವಿಲ್ಲದ ನಕ್ಷೆಯನ್ನು ಬಳಸುತ್ತೇವೆ. ನಾವು ಎರಡು ನೆಸ್ಟೆಡ್ ಲೂಪ್‌ಗಳನ್ನು ಬಳಸುತ್ತೇವೆ, ಅದು ಇತ್ ಇಂಡೆಕ್ಸ್‌ನಲ್ಲಿರುವ ಸ್ಟ್ರಿಂಗ್ ಜೆತ್ ಇಂಡೆಕ್ಸ್‌ನಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್‌ನ ಸಬ್‌ಸ್ಟ್ರಿಂಗ್ ಆಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತದೆ ಮತ್ತು ಪ್ರತಿಯಾಗಿ. ಸಿ ++ ನಲ್ಲಿ, ನಾವು ನಮ್ಮದೇ ಆದ ಕಾರ್ಯವನ್ನು ರಚಿಸಿದ್ದೇವೆ ಅದು ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್ ಮೊದಲ ಆರ್ಗ್ಯುಮೆಂಟ್‌ನ ಸಬ್‌ಸ್ಟ್ರಿಂಗ್ ಆಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತದೆ. ಜಾವಾದಲ್ಲಿ, ಒಳಗೊಂಡಿರುವ () ಕಾರ್ಯವನ್ನು ಬಳಸಿಕೊಂಡು ಇದನ್ನು ಸುಲಭವಾಗಿ ಕಾಣಬಹುದು.

ಅರೇ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಹೊಂದಾಣಿಕೆಗಾಗಿ ಕೋಡ್

ಸಿ ++ ಕೋಡ್

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

bool isSubstr(string a, string b){
    int n = a.size(), m = b.size();
    for(int i=0;i<=n-m;i++){
        if(a.substr(i, m) == b)
            return true;
    }
    return false;
}

vector<string> stringMatching(vector<string>& words) {
    unordered_set<string> tmp;
    int n = words.size();
    for(int i=0;i<n-1;i++){
        string curWord = words[i];
        for(int j=i+1;j<n;j++){
            string nextWord = words[j];
            if(isSubstr(curWord, nextWord))
                tmp.insert(nextWord);
            if(isSubstr(nextWord, curWord))
                tmp.insert(curWord);
        }
    }
    return vector<string>(tmp.begin(), tmp.end());
}

int main(){
    vector<string> input({"mass","as","hero","superhero"});
    vector<string> v = stringMatching(input);
    for(auto x: v)
        cout<<x<<" ";
}
hero as

ಜಾವಾ ಕೋಡ್

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

class Main
{
  public static List<String> stringMatching(String[] words) {
        HashSet<String> tmp = new HashSet<>();
        
        int n = words.length;
        for(int i = 0; i<n-1; i++) {
            String curWord = words[i];
            for(int j = i+1; j<n; j++) {
                String nextWord = words[j];
                if(curWord.contains(nextWord))
                    tmp.add(nextWord);
                if(nextWord.contains(curWord))
                    tmp.add(curWord);
            }
        }
        
        return new ArrayList<String>(tmp);
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    String[] words = {"mass","as","hero","superhero"};
    List<String> list = stringMatching(words);
    for(String x: list)
      System.out.print(x+" ");
  }
}
hero as

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯದ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ ^ 2 * | ಎಸ್ |), ಏಕೆಂದರೆ ನಾವು ಇನ್ಪುಟ್ ತಂತಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅವಲಂಬಿಸಿರುವ ಎರಡು ನೆಸ್ಟೆಡ್ ಲೂಪ್ಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ. ಸ್ಟ್ರಿಂಗ್ ಇತರ ಅಗತ್ಯಗಳ ತಲಾಧಾರವಾಗಿದೆಯೇ ಎಂದು ಕಂಡುಹಿಡಿಯಲು ಬಳಸುವ ಕಾರ್ಯ ಒ (| ಎಸ್ |) ಸಮಯ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಇಡೀ ಇನ್ಪುಟ್ output ಟ್ಪುಟ್ ಆಗಿರಬಹುದು. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.