关键字：“字符串”、“字母异位词”、“分析”

题目描述

字母异位词分组

分析

对于这道题目主要有两个问题需要解决：

1. 如何判断两个字符串时字母异位词

2. 如何将相同的字母异位词放入同一个数组中

对于问题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

数据结构

1. 从feature到class_idx的映射： map、hashmap

2. 存储各类字符串的数组：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.

1. 相比较于其他已有的leetcode刷题笔记，我希望能够提供相关的解题分析和部分相关问题的链接，使得大家能获得一个较好的分析与相关问题的比较。

2. 偶尔会进行类似题目的总结工作，有需要的读者可以对这份工作进行关注。

3. 如果你发现有相关的错误或者表述不当不清晰的地方，请进行评论，我会尽快进行核对勘正。