首页 > 代码库 > LeetCode--Anagrams
LeetCode--Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
先将原字符串数组中的字符串单独排序,如:bac-->abc,然后对整个的数组排序,此时数组中相邻的字符串如果相等,则原数组中的两字符串必满足条件,将其加入到结果数组中。题中使用了堆排序对单个字符创排序,由于经过单个字符串排序之后,字符串数组中存在很多重复的元素,因此采用三向切分快速排序对字符串数组进行排序。
Solution
class Solution { public: vector<string> anagrams(vector<string> &strs) { vector<string> temp = strs; int n=temp.size(); vector<string> res; if(n == 0 || n==1) return res; vector<int> index; for(int i=0; i<n; i++) { index.push_back(i); heap_sort(temp[i]); } quicksort(temp,index,0,n-1); string flag = temp[index[0]]; int count = 1; int i; for(i=0; i<n-1; i++) { if(temp[index[i]] == temp[index[i+1]]) { res.push_back(strs[index[i]]); count++; } else { if(count>1) res.push_back(strs[index[i]]); count = 1; flag = temp[index[i]]; } } if(count>1) res.push_back(strs[index[i]]); return res; } void swap(string& s, int i, int j) { char temp = s[i]; s[i] = s[j]; s[j] = temp; } void sink(string& s, int loc, int end) { while(loc < end) { int k=2*loc+1; if(k>end) return; if(k<end && s[k]<s[k+1]) k++; if(s[k]<s[loc]) return ; swap(s,loc,k); loc = k; } } void heap_sort(string& s) { int n = s.length()-1; for(int i=(n-1)/2; i>=0; i--) sink(s,i,n); while(n>0) { swap(s,0,n); n--; sink(s,0,n); } } void quicksort(vector<string>& s, vector<int>& index, int low, int high) { if(low>=high) return; int lt = low; int ht = high; int l = low+1; string hold = s[index[low]]; while(l<=ht) { if(s[index[l]] <= hold) swap(index,lt++,l++); else swap(index,l,ht--); } quicksort(s,index,low,lt-1); quicksort(s,index,ht+1,high); } void swap(vector<int>& index, int i, int j) { int temp = index[i]; index[i] = index[j]; index[j] = temp; } };
LeetCode--Anagrams
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。