組字謎


難度級別
經常問 亞馬遜 Facebook 谷歌 Microsoft微軟
哈希

我們必須找出給定單詞的組字謎。 這意味著我們要為每個單詞 分類 並將其存儲為鍵和原始輸入(不按值排序),並且如果其他任何輸入具有與先前排序的字符串相同的值,我們將存儲在相同的鍵上,但具有不同的值,為此,向量作為參數傳遞給out函數,在其中我們將執行所有操作。

字謎:通過重新排列另一個單詞的所有字母而創建的單詞被稱為字謎。

例子:吃,吃,喝茶是彼此的字謎

在這個問題上,您得到一些提示。 您的任務是將這些單詞彼此組成一個詞組。

輸入: 吃,茶,棕褐色,吃,納特,蝙蝠

輸出: [吃,茶,吃],[棕褐色],[蝙蝠]

算法

  1. 聲明地圖變量mymap,向量 >變量final_set。
  2. 在循環中,獲取鍵中的輸入值並對它們進行排序
  3. 將input [i]的值推回映射的鍵(已排序的字符串)。
  4. 使用for-each推回值到最終集合中。
  5. 打印最後一組。

解釋

首先,我們的輸入 Wi-Fi: 其中所有輸入值都作為參數存儲在其中。 在這裡,我們聲明一張地圖, 向量 分別是my_map和final_set的vectors變量。 進入for循環,該循環迭代向量,直到達到向量的大小為止。 在此循環中,我們將把每個輸入索引的值放入鍵中。

我們將對鍵中的值存儲進行排序,以便我們可以將其作為字謎進行檢查,然後將input [i]的值放入映射中鍵為已排序字符串的鍵位置。 一直進行到我們迭代輸入集中的所有值為止。 並將所有鍵值存儲在地圖中,

然後,我們將my_map的所有值添加到向量的最終集合向量中。 最後,打印出來。

假設輸入:[飲食,茶,棕褐色,鹽,堅果,蝙蝠]

排序鍵= aet

以aet作為關鍵,進餐將作為一種價值來存儲

再次,茶的排序關鍵字是aet將作為關鍵字存儲,並作為茶來存儲值。

完成所有迭代後:

aet(排序的字符串):[吃,茶,吃] //鍵值對

ant(排序的字符串):[tan,ant] //鍵/值對

abt(排序字符串):[bat] //鍵/值對

最後,我們得到了輸出。

履行

組圖的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 ]
]

組圖的Java程序

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]

組圖的複雜度分析

時間複雜度

O(NM) 其中N是單詞數,M是每個單詞的最大字符數。

空間複雜度

O(N + M) 其中N是單詞數,M是每個單詞的最大字符數。