String တစ်ခု Array Leetcode Solution တွင်ကိုက်ညီခြင်း


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ
ကြိုး

Array Leetcode Solution တွင် String Matching ပြနာကကျွန်တော်တို့ကို strings များစွာပေးသည်။ ပြနာကကျွန်တော်တို့ကိုအခြားအရာ၏အစွန်အဖျားများဖြစ်သောညှို့များကိုရှာဖွေရန်ပြောပါသည် ကြိုး input ကိုကနေ။ သတိပေးချက်တစ်ခုအနေဖြင့်၊ substring သည်အဆုံးသတ်နှစ်ခုစလုံးမှအက္ခရာများကိုဖယ်ရှားပြီးနောက်ကျန်ရှိနေသော string ၏အစိတ်အပိုင်းတစ်ခုဖြစ်သည်။ အဆုံးသတ်နှစ်ခုစလုံးမှအက္ခရာ 0 လုံးကိုလည်းသင်ဖယ်ရှားနိုင်သည်။ ဖယ်ရှားခံထားရသောစာလုံးအရေအတွက်သည်လည်းအတူတူမလိုအပ်ပါ။ ဒါကြောင့်ပိုကောင်းတဲ့နားလည်မှုအတွက်ဥပမာအချို့ကိုလေ့လာကြည့်ကြစို့။

String တစ်ခု Array Leetcode Solution တွင်ကိုက်ညီခြင်း

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

ရှင်းလင်းချက် -“ အစုလိုက်အပြုံလိုက်” ထွက်လာတာကြောင့် output က“ as” ရှိတယ်။ အလားတူပင်“ သူရဲကောင်း” သည်“ စူပါဟီးရိုး” ၏အစိတ်အပိုင်းတစ်ခုဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ထည့်သွင်းမှု၏သွင်းအားစုများကိုအလွယ်တကူတွေ့ရှိခဲ့သည်။

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

ရှင်းလင်းချက် - ဒီဥပမာက substrings ဟာ string တစ်ခုတည်းကနေဖြစ်နိုင်တယ်ဆိုတာပြတယ်။ ဒီမှာလိုပဲ output မှာရှိတဲ့ string နှစ်ခုလုံးက“ leetcode” ရဲ့ substring ဖြစ်တယ်။

Array Leetcode Solution တွင် String Matching အတွက်ချဉ်းကပ်မှု

ပြproblemနာကကျွန်တော်တို့ကိုသတ်သတ်မှတ်မှတ်အခြေအနေတစ်ခုကိုဖြည့်ဆည်းပေးနိုင်တဲ့ input ထဲကနေကြိုးတွေကိုရွေးဖို့ပြောခဲ့တယ်။ အခြေအနေက string ကို input ထဲမှာပါတဲ့ string ရဲ့ substring ဖြစ်သင့်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်အခြား string တစ်ခု၏ substring နေသော string များကိုရှာဖွေသည့်ဤဖြစ်စဉ်ကိုကျွန်ုပ်တို့ကြိုးစားတုပသည်။ ကျန်ရှိနေသေးသောတစ်ခုတည်းသောရှုပ်ထွေးမှုမှာအကောင်အထည်ဖော်မှုဖြစ်သည် ထို့ကြောင့်ကျွန်ုပ်တို့သည် output များအနေဖြင့်ဆောင်ရွက်မည့် strings များကိုခြေရာခံရန် hashset သို့မဟုတ် unordered map ကိုအသုံးပြုသည်။ nth loops နှစ်ခုကိုအသုံးပြုသည်။ ith index မှာရှိတဲ့ string သည် jth index မှာရှိသလား။ အပြန်အလှန်လားဆိုတာကိုစစ်ဆေးသည်။ C ++ တွင်၊ ဒုတိယ string သည်ပထမ argument ၏ substring ဟုတ်မဟုတ်စစ်ဆေးသည့်ကျွန်ုပ်တို့၏ကိုယ်ပိုင် function ကိုဖန်တီးခဲ့သည်။ Java တွင်၎င်းကို (() function ကိုအလွယ်တကူရှာဖွေနိုင်သည်။

Array Leetcode Solution တွင် String Matching အတွက် Code

C ++ ကုဒ်

#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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N ^ 2 * | S |), ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ input strings အရေအတွက်ပေါ်မူတည်ပြီးအသိုက်လုပ်ထားတဲ့ loops နှစ်ခုကိုအသုံးပြုခဲ့လို့ပဲ။ ထိုအခါ function ကို string ကိုအခြားလိုအပ်ချက်များ၏ substring ဟုတ်မဟုတ်ကိုရှာဖွေလေ့ရှိတယ် အို (| S |) အချိန်။

အာကာသရှုပ်ထွေးမှု

အို (N)၊ အဆိုးဆုံး - ကိစ္စတွင်သွင်းအားစုတစ်ခုလုံးသည်ထွက်ရှိနိုင်သည်။ အရှင်အာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။