# 組字謎

## 算法

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

## 解釋

### 例

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是每個單詞的最大字符數。