关键字：“字符串”、“字母异位词”、“分析”
题目描述
分析
对于这道题目主要有两个问题需要解决：
如何判断两个字符串时字母异位词
如何将相同的字母异位词放入同一个数组中
对于问题1：
判定方式1：对于两个字符串，排序后的结果如果是相同的两个字符串，则为字母异位词
判定方式2：由于题目说明所有输入均为小写字母，可以用长度为26的数组来计数各个字母出现的次数。对于两个字符串，如果对应的计数数组的各个位置均相同，则这两个字符串为字母异位词
方式1中排序后的数组或方式2中计数数组，抽象为特征，每个不同的特征对应一个等价类，对所有的字符串进行分类（各类别之间互不相交且并集为全集）。
对于问题2
使用从判定相同字符串的依据作为key，对应存储数组的索引作为value的哈希表。#map（c++）、hashmap (java) 、dict (python)
总
有了特征这个概念，该题目可以清晰地看作是分类问题，根据不同字符串地特征来进行互不相交地分类。
字符串 --> 特征--> 对应类;
解题思路
输入为字符串数组
输出为字符串数组的集合
对于字符串数组中的每个字符串，对该字符串进行排序，对于排序结果
，判断是否已经存在于哈希表中。如果不在哈希表中，建立从该排序后的字符串
到存储字符串数组集合索引的映射，并将原数组进行存储。
算法
INPUT: strs (list of string)
OUTPUT: set of different classification
feature_class_map = {}
class_idx = 0
for str in strs :
feature = extract_feature( str ) #可两种不同特征
if feature_class_map.find(feature) != feature_class_map.end() :
class_idx= feature_class_map[ feature ]
set[class_idx].push_back( str )
else :
feature_class_map[ feature ] = class_idx
class_idx ++
return set
############feature1##############
func extract_feature1( str ):
str1 = sort( str )
return str1
############feature2##############
func extract_feature2( str ):
count = []
for zifu in str :
count[zifu-'a'] ++
return count
数据结构
从feature到class_idx的映射： map、hashmap
存储各类字符串的数组：vector
复杂度分析
设字符串长度为k
排序 O(klog(k)) + 哈希表映射 O(1)
代码实现
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans ;
map<string, int> m ;
int count = 0 ;
for ( string str : strs ){
string sorted_str = str ;
sort( sorted_str.begin(), sorted_str.end() ) ;
if ( m.find(sorted_str) != m.end() ){
ans[ m[sorted_str] ].push_back( str ) ;
}else{
m[sorted_str] = count ;
vector<string> tmp ;
tmp.push_back( str ) ;
ans.push_back( tmp ) ;
++ count ;
}
}
return ans ;
}
};
相关问题
PS.
相比较于其他已有的leetcode刷题笔记，我希望能够提供相关的解题分析和部分相关问题的链接，使得大家能获得一个较好的分析与相关问题的比较。
偶尔会进行类似题目的总结工作，有需要的读者可以对这份工作进行关注。
如果你发现有相关的错误或者表述不当不清晰的地方，请进行评论，我会尽快进行核对勘正。
