同字符字符串归类 - 代码练习
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
All inputs will be in lowercase.
The order of your output does not matter.
C++:
方案：
class Solution
{
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string, vector<string>> check;
for (auto s : strs) {
std::string sorted = s;
std::sort(sorted.begin(), sorted.end());
check[sorted].push_back(s);
}
vector<vector<string>> result;
result.reserve(check.size());
for (auto kv : check) {
result.push_back(kv.second);
}
return result;
}
};
测试案例：
TEST_METHOD(TestMethod1) {
Solution solution;
string strs[] = { "eat", "tea", "tan", "ate", "nat", "bat" };
vector<string> strs1;
strs1.insert(strs1.begin(), std::begin(strs), std::end(strs));
vector<vector<string>> result = solution.groupAnagrams(strs1);
vector<vector<string>> expected;
string s1[] = { "eat", "tea", "ate"};
string s2[] = { "tan", "nat" };
string s3[] = { "bat" };
vector<string> ss1;
vector<string> ss2;
vector<string> ss3;
ss1.insert(ss1.begin(), std::begin(s1), std::end(s1));
ss2.insert(ss2.begin(), std::begin(s2), std::end(s2));
ss3.insert(ss3.begin(), std::begin(s3), std::end(s3));
expected.push_back(ss1);
expected.push_back(ss2);
expected.push_back(ss3);
Assert::AreEqual(result.size(), expected.size());
vector<string> list1;
vector<string> list2;
for (auto y : result) {
for (auto x : y) {
list1.push_back(x);
}
}
for (auto y : expected) {
for (auto x : y) {
list2.push_back(x);
}
}
sort(list1.begin(), list1.end());
sort(list2.begin(), list2.end());
for (uint32_t i = 0; i < list1.size(); i++) {
Assert::AreEqual(list1[i], list2[i]);
}
}
C#:
方案：
public class Solution
{
public IList<IList<string>> GroupAnagrams(string[] strs)
{
Dictionary<string, IList<string>> check = new Dictionary<string, IList<string>>();
foreach(string s in strs)
{
char[] a = s.ToCharArray();
Array.Sort(a);
string sorted = new string(a);
if (!check.ContainsKey(sorted))
{
check.Add(sorted, new List<string>());
}
check.GetValueOrDefault(sorted).Add(s);
}
return check.Values.ToList(); ;
}
}
测试案例：
[TestMethod()]
public void Test1()
{
Solution solution = new Solution();
String[] strs = { "eat", "tea", "tan", "ate", "nat", "bat" };
IList<IList<String>> result = solution.GroupAnagrams(strs);
List<String> l1 = new List<string>()
{
"ate","eat","tea"
};
List<String> l2 = new List<string>() { "nat", "tan" };
List<String> l3 = new List<string>() { "bat" };
List<List<String>> expected = new List<List<String>>() { l1, l2, l3 };
List<String> listCheck1 = new List<string>();
List<String> listCheck2 = new List<string>();
foreach(IList<string> y in result)
{
foreach(string x in y)
{
listCheck1.Add(x);
}
}
foreach (IList<string> y in expected)
{
foreach (string x in y)
{
listCheck2.Add(x);
}
}
listCheck1.Sort();
listCheck2.Sort();
Assert.AreEqual(listCheck1.Count, listCheck2.Count);
for(int i = 0;i < listCheck1.Count; i ++)
{
Assert.AreEqual(listCheck1[i], listCheck2[i]);
}
}
}
Go
func groupAnagrams(strs []string) [][]string {
check := make(map[string][]string)
for _, s := range strs {
sortedArray := strings.Split(s, "")
sort.Strings(sortedArray)
sorted := strings.Join(sortedArray, "")
value, ok := check[sorted]
if !ok {
check[sorted] = []string{}
value = []string{}
}
value = append(value, s)
check[sorted] = value
}
result := [][]string{}
for _, v := range check {
result = append(result, v)
}
return result
}
方案：
测试案例：
func Test_groupAnagrams(t *testing.T) {
type args struct {
strs []string
}
a1 := []string{"ate", "eat", "tea"}
a2 := []string{"nat", "tan"}
a3 := []string{"bat"}
expected := [][]string{}
expected = append(expected, a1)
expected = append(expected, a2)
expected = append(expected, a3)
tests := []struct {
name string
args args
want [][]string
}{
{"test1", args{strs: []string{"eat", "tea", "tan", "ate", "nat", "bat"}}, expected},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
got := groupAnagrams(tt.args.strs)
list1 := []string{}
list2 := []string{}
for _, e := range got {
for _, x := range e {
list1 = append(list1, x)
}
}
for _, e := range tt.want {
for _, x := range e {
list2 = append(list2, x)
}
}
sort.Strings(list1)
sort.Strings(list2)
if !reflect.DeepEqual(list1, list2) {
t.Errorf("groupAnagrams() = %v, want %v", list1, list2)
}
})
}
}
Java:
方案：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<List<String>>();
Map<String, ArrayList<String>> check = new HashMap<>();
for(String s : strs) {
String sorted = Stream.of(s.split("")).sorted().collect(Collectors.joining());
if(!check.containsKey(sorted)) {
check.put(sorted, new ArrayList<String>());
}
check.get(sorted).add(s);
}
result = check.values().stream().collect(Collectors.toList());
return result;
}
}
测试案例：
@Test
public void test1() {
Solution solution = new Solution();
String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> result = solution.groupAnagrams(strs);
List<List<String>> expected = new ArrayList<List<String>>();
List<String> l1 = new ArrayList<>();
l1.add("ate");
l1.add("eat");
l1.add("tea");
List<String> l2 = new ArrayList<>();
l2.add("nat");
l2.add("tan");
List<String> l3 = new ArrayList<>();
l3.add("bat");
expected.add(l1);
expected.add(l2);
expected.add(l3);
List<String> listCheck1 = new ArrayList<>();
List<String> listCheck2 = new ArrayList<>();
result.stream().forEach(y->{
y.stream().forEach(x->{
listCheck1.add(x);
});
});
expected.stream().forEach(y->{
y.stream().forEach(x->{
listCheck2.add(x);
});
});
Collections.sort(listCheck1);
Collections.sort(listCheck2);
Assert.assertEquals(listCheck1, listCheck2);
}
Javascript
方案：
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
let check = {}
strs.forEach(s=>{
let sorted = s.split('').sort().join('');
if(!check[sorted]){
check[sorted] = [];
}
check[sorted].push(s);
});
return Object.values(check);
};
测试案例：
it("test1", function () {
// 1. ARRANGE
let strs = ["eat", "tea", "tan", "ate", "nat", "bat"];
let expected = [["ate", "eat", "tea"], ["nat", "tan"], ["bat"]];
// 2. ACT
let result = groupAnagrams(strs);
// 3. ASSERT
expectedList = [];
expected.forEach(e => {
e.forEach(v=>{
expectedList.push(v);
})
});
resultList = [];
result.forEach(e => {
e.forEach(v=>{
resultList.push(v);
})
});
resultList = resultList.sort();
expectedList = expectedList.sort();
expect(expectedList.length).to.be.equal(resultList.length);
for(let i = 0 ; i < expectedList.length; i ++) {
expect(expectedList[i]).to.be.equal(resultList[i]);
}
});
Kotlin:
方案：
class Solution {
fun groupAnagrams(strs: Array<String>): List<List<String>> {
val check: MutableMap<String, ArrayList<String>> = HashMap()
for (s in strs) {
var charArray = s.toCharArray()
Arrays.sort(charArray)
val sorted = String(charArray)
if (!check.containsKey(sorted)) {
check[sorted] = ArrayList()
}
check[sorted]?.add(s)
}
var result = check.values.stream().collect(Collectors.toList())
return result
}
}
测试案例：
@Test
fun test1() {
val solution = Solution()
val strs = arrayOf("eat", "tea", "tan", "ate", "nat", "bat")
val result = solution.groupAnagrams(strs)
val l1: MutableList<String> = arrayListOf("ate", "eat", "tea")
val l2: MutableList<String> = arrayListOf("nat", "tan")
val l3: MutableList<String> = arrayListOf("bat")
val expected: MutableList<List<String>> = arrayListOf(l1, l2, l3)
val listCheck1: MutableList<String> = ArrayList()
val listCheck2: MutableList<String> = ArrayList()
result.stream().forEach { y: List<String> -> y.stream().forEach { x: String -> listCheck1.add(x) } }
expected.stream().forEach { y: List<String> -> y.stream().forEach { x: String -> listCheck2.add(x) } }
listCheck1.sort()
listCheck2.sort()
Assert.assertEquals(listCheck1, listCheck2)
}
Python3:
方案：
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
check = {}
for s in strs:
l = list(s)
l.sort()
sorted = "".join(l)
if sorted not in check:
check[sorted] = []
check[sorted].append(s)
return list(check.values())
测试案例：
def test1(self):
s = Solution()
a = [ "eat", "tea", "tan", "ate", "nat", "bat" ]
expected = [["ate", "eat", "tea"], ["nat", "tan"], ["bat"]]
result = s.groupAnagrams(a)
list1 = []
list2 = []
for y in expected:
for x in y:
list1.append(x)
for y in result:
for x in y:
list2.append(x)
list1.sort()
list2.sort()
self.assertEqual(list1, list2)
Rust
方案：
impl Solution {
pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
let len = strs.len();
let mut check: HashMap<String, Vec<String>> = HashMap::new();
for i in 0..len {
let s = &strs[i];
let mut char_vec: Vec<char> = s.chars().collect();
char_vec.sort_by(|a, b| b.cmp(a));
let sorted = char_vec.iter().cloned().collect::<String>();
check
.entry(sorted)
.or_insert(Vec::new())
.push(s.to_string());
}
let mut result: Vec<Vec<String>> = Vec::new();
for (_, val) in check.iter_mut() {
result.push((*val).to_vec());
}
return result;
}
}
测试案例：
#[test]
fn test1() {
let vec: Vec<String> = vec![
"eat".to_string(),
"tea".to_string(),
"tan".to_string(),
"ate".to_string(),
"nat".to_string(),
"bat".to_string(),
];
let mut expected: Vec<Vec<String>> = Vec::new();
expected.push(vec![
"ate".to_string(),
"eat".to_string(),
"tea".to_string(),
]);
expected.push(vec!["nat".to_string(), "tan".to_string()]);
expected.push(vec!["bat".to_string()]);
let result = Solution::group_anagrams(vec);
assert_eq!(result.len(), expected.len());
let mut list1: Vec<String> = Vec::new();
let mut list2: Vec<String> = Vec::new();
for y in &result {
for x in y {
list1.push(x.to_string());
}
}
for y in &expected {
for x in y {
list2.push(x.to_string());
}
}
list1.sort();
list2.sort();
assert_eq!(list1, list2);
}
- 点赞
- 收藏
- 关注作者
评论（0）