题目

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

 

思路

1. 使用数组模拟哈希表, 数组下标0-25分别代表字符'a'-'z', a[0] 代表 'a' 在单词中出现的次数

2. 排序, 只有相邻的单词才有可能是相同的

3. 这么慢的方法没想到 176ms 就能通过

 

总结

1. word 起初没有对 char 数组初始化, 结果 VS 成功运行, 但 Leetcode 上却是 WA. VS 真是宠坏一批程序员

 

代码

class word {public:	word() {		memset(chars, 0, sizeof(chars));		index = 0;	}	int chars[26];	int index;	bool operator<(const word &ths) const {		for(int i = 0; i < 26; i ++) {			if(this->chars[i] != ths.chars[i]){				return this->chars[i] < ths.chars[i];			}		}		return this->index < ths.index;	}	bool operator==(const word &ths) const {		for(int i = 0; i < 26; i ++) {			if(this->chars[i] != ths.chars[i]) {				return false;			}		}		return true;	}};class Solution {public:    vector
          
            anagrams(vector
           
             &strs) {		vector
            
              record;		for(int i = 0; i < strs.size(); i ++) {			record.push_back(buildWord(strs[i], i));		}		sort(record.begin(), record.end());		vector
             
               res;		bool flag = false;		for(int i = 1; i < record.size(); i ++) {			if(record[i] == record[i-1]) {				if(!flag) {					res.push_back(record[i-1]);					res.push_back(record[i]);					flag = true;				}else{					res.push_back(record[i]);				}			}else{				flag = false;			}		}		return decomposition(res, strs);    }	word buildWord(const string &str, const int &index) {		word newword;		for(int i = 0; i < str.size(); i ++) {			newword.chars[str[i]-'a'] ++;		}		newword.index = index;		return newword;	}	vector
              
                decomposition(vector
               
                 &vec, vector
                
                  &strs) { vector
                 
                   res; for(int i = 0; i < vec.size(); i++) { res.push_back(strs[vec[i].index]); } return res; }};