Group မှ Anagrams


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Facebook က Google Microsoft က
တားဆီးခြင်း ကြိုး

ပေးထားသောစကားလုံးများ၏အုပ်စုလိုက်ပုံကြမ်းများကိုရှာဖွေရန်လိုသည်။ ဆိုလိုသည်မှာကျွန်ုပ်တို့သည်သွားမည့်စကားလုံးတိုင်းအတွက်ဖြစ်သည် ကြမ္မာ ၎င်းကို၎င်းကိုတန်ဖိုးတစ်ခုအဖြစ်မသတ်မှတ်ထားသောသော့နှင့်မူရင်းထည့်သွင်းမှုတစ်ခုအနေနှင့်သိုလှောင်သိမ်းဆည်းပါ။ အခြားထည့်သွင်းမှုတစ်ခုသည်ယခင်ကခွဲထားသော string နှင့်အတူတူပင်တူတူပင်ဖြစ်ပါကကျွန်ုပ်တို့သည်တူညီသောသော့တစ်ခုတွင်သိုလှောင်ထားမည်ဖြစ်သော်လည်းကွဲပြားခြားနားသောတန်ဖိုးတစ်ခုအနေဖြင့်၊ Vector အားစစ်ဆင်ရေးအားလုံးကိုလုပ်ဆောင်တော့မည့်အငြင်းအခုံအဖြစ်အငြင်းအခုံပြုသည်။

ပုံကြမ်း: အခြားစကားလုံးများ၏အက္ခရာများအားလုံးကိုပြန်လည်စီစဉ်ခြင်းဖြင့်ဖန်တီးထားသောစကားလုံးများကို anagrams ဟုခေါ်သည်။

ဥပမာ - စား၊ စားပါ၊

ဒီပြproblemနာမှာမင်းကိုစကားလုံးတချို့ပေးတယ်။ သင်၏တာဝန်မှာစကားလုံးများကိုတစ်ခုနှင့်တစ်ခုဖွဲ့စည်းရန်အုပ်စုတစ်ခုတွင်စီစဉ်ရန်ဖြစ်သည်။

နမူနာ

input: စားပါ၊ လက်ဖက်၊ tan၊ စား၊ nat၊ လင်းနို့

output: [စားသောက်၊ လက်ဖက်ရည်၊ စားသည်၊ [tan, nat], [bat]

algorithm

  1. မြေပုံပြောင်းလဲနိုင်သော mymap, vector ဖြစ်သည် > variable ကို final_set ။
  2. ကွင်းဆက်တစ်ခုအတွင်းရှိ input တန်ဖိုးများကိုသော့ ယူ၍ ယူပါ
  3. [i] ထည့်သွင်းခြင်း၏တန်ဖိုးကိုမြေပုံ၏သော့ချက် (အစဉ်လိုက်စီထားသည့် string) သို့ပြန်ပို့ပါ။
  4. အဘို့ - တစ်ခုချင်းစီကို pushback တန်ဖိုးကိုနောက်ဆုံးအစုံသို့အသုံးပြုခြင်း။
  5. နောက်ဆုံး set ကိုပုံနှိပ်ပါ။

ရှင်းလင်းချက်

ပထမတော့ကျွန်တော်တို့ရဲ့ input ကို အစုံ အားလုံးကျွန်တော်တို့ရဲ့ input ကိုတန်ဖိုးများကိုတစ် ဦး parameter သည်အဖြစ်လွန်အတွက်သိမ်းထားတဲ့နေကြသည်။ ဒီမှာမြေပုံတစ်ခုကြေငြာတယ် အားနည်းချက်ကို အသီးသီး my_map နှင့် final_set ၏ virus သယ်ဆောင်၏ variable ကို၏။ vector ၏အရွယ်အစားမရောက်မချင်း vector ကို iterates ဖြစ်သော loop အတွက်လာပါ။ ဒီကွင်းဆက်မှာ input တစ်ခုစီရဲ့တန်ဖိုးကိုသော့တစ်ချပ်ထဲထည့်လိုက်မယ်။

value ကို store လုပ်ရန်အတွက်၎င်းကို anagram အဖြစ်စစ်ဆေးပြီး input [i] ၏တန်ဖိုးကိုမြေပုံ၏သော့နေရာတွင်ထည့်သွင်းပြီး၎င်းသည် string ကိုစီထားသော string တစ်ခုအဖြစ်ထားနိုင်သည်။ ကျနော်တို့ input ကို set အတွက်အားလုံးတန်ဖိုးများကိုကြားမှာသည်အထိဤသည်ဆက်လက်ပါလိမ့်မယ်။ ပြီးတော့မြေပုံထဲမှာသော့ချက်တန်ဖိုးတွေအားလုံးကိုသိမ်းဆည်းထားပါ။

ထို့နောက် my_map ၏တန်ဖိုးအားလုံးကိုနောက်ဆုံး set vector ၏векторထဲသို့ထည့်ပါမည်။ နောက်ဆုံးကပုံနှိပ်ထုတ်ပါ။

နမူနာ

input ကိုဆိုပါစို့။ [စားပါ၊ လက်ဖက်ရည်၊ tan၊ စား၊ nat၊ လင်းနို့]

သော့ချက် = aet စီထားသော

aet အတွက်သော့ချက်အဖြစ်စားခြင်းသည်တန်ဖိုးတစ်ခုအဖြစ်သိုလှောင်ထားသည်

နောက်တဖန်လက်ဖက်ရည်အမျိုးအစားခွဲခြားထားသည့်အဓိကအချက်မှာလက်ဖက်ရည်ကဲ့သို့သော့ချက်အဖြစ်သိုလှောင်ထားသည့် aet ဖြစ်သည်။

အားလုံးကြားမှာလုပ်နေပြီးနောက်:

aet (စီထားသောကြိုး) - စား၊ လက်ဖက်ရည်၊ စား

ပုရွက်ဆိတ် (Sorted string ကို): [tan, ပုရွက်ဆိတ်] // သော့ချက်တန်ဖိုး pair တစုံ

abt (Sorted string): [လင်းနို့] // key- တန်ဖိုးကို pair တစုံ

နောက်ဆုံးတော့ output ကိုရတယ်။

အကောင်အထည်ဖော်ရေး

Group မှ Anagram များအတွက် C ++ အစီအစဉ်

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

vector<vector<string> > groupAnagrams(vector<string>& input_set)
{
    // the first value will hold the key,
    //the second vector is used to hold the multiple values.
    unordered_map<string, vector<string>> my_map;
    vector<vector<string> > final_set;

    for (int i = 0; i < input_set.size(); i++)
    {
        // take value at the index as a key
        string key = input_set[i];

        //sort the key
        sort(key.begin(), key.end());

        // add the value to that key
        my_map[key].push_back(input_set[i]);

    }

    for (auto n : my_map)
    {
        // add all the values in the map to the final set
        final_set.push_back(n.second);
    }

    return final_set;
}

int main()
{
    vector<string> input_set;
    input_set.push_back("eat");
    input_set.push_back("tea");
    input_set.push_back("tan");
    input_set.push_back("ate");
    input_set.push_back("nat");
    input_set.push_back("bat");

    vector<vector<string> > final_set =  groupAnagrams(input_set);

    // print the output
    cout<<" [ "<<endl;
    for (int i = 0; i < final_set.size(); i++)
    {
        if (final_set[i].size() > 0)
        {
            cout << "  [";
            for (int j = 0; j < final_set[i].size(); j++)
                cout<< final_set[i][j]<<" ";
            cout << "]";
        }
        cout<<endl;
    }
    cout<<" ] ";

    return 0;
}
[
 [bat ]
 [tan nat ]
 [eat tea ate ]
]

Group မှ Anagram များအတွက် Java program

import java.util.*;
import java.util.stream.Collectors;

class findGroupAnagrams
{
  public static void getgroup(String[] words)
  {
    List<String> myList = Arrays.stream(words)
        .map(s -> s.toCharArray())
        .map(chars -> { Arrays.sort(chars); return new String(chars); })
        .collect(Collectors.toList());
    Map<String, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < myList.size(); i++)
    {
      map.putIfAbsent(myList.get(i), new ArrayList<>());
      map.get(myList.get(i)).add(i);
    }
    for (var entry: map.entrySet()) {
      System.out.println(entry.getValue().stream()
              .map(index -> words[index])
              .collect(Collectors.toList()));
    }
  }
  public static void main(String[] args)
  {
    String[] input = {"eat","tea","tan","ate","nat","bat"};
    getgroup(input);
  }
}
[eat, tea, ate]
[bat]
[tan, nat]

Group မှ Anagrams များအတွက်ရှုပ်ထွေးအားသုံးသပ်ခြင်း

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

အို (မင်) N သည်စကားလုံးအရေအတွက်နှင့် M သည်စာလုံးတစ်လုံးစီတွင်အများဆုံးအက္ခရာဖြစ်သည်။

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

အို (N + M) N သည်စကားလုံးအရေအတွက်နှင့် M သည်စာလုံးတစ်လုံးစီတွင်အများဆုံးအက္ခရာဖြစ်သည်။