leetcode 893. Groups of Special-Equivalent Strings

本文主要是介绍leetcode 893. Groups of Special-Equivalent Strings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接

You are given an array of strings of the same length words.

In one move, you can swap any two even indexed characters or any two odd indexed characters of a string words[i].

Two strings words[i] and words[j] are special-equivalent if after any number of moves, words[i] == words[j].

For example, words[i] = "zzxy" and words[j] = "xyzz" are special-equivalent because we may make the moves "zzxy" -> "xzzy" -> "xyzz".

A group of special-equivalent strings from words is a non-empty subset of words such that:

Every pair of strings in the group are special equivalent, and
The group is the largest size possible (i.e., there is not a string words[i] not in the group such that words[i] is special-equivalent to every string in the group).

Return the number of groups of special-equivalent strings from words.

按奇偶位置顺序重新排列字符串，然后统计有多少个不重复的字符串

class Solution {
public:int numSpecialEquivGroups(vector<string>& words) {unordered_map<string,bool> mp;for (int i = 0; i< words.size(); i ++) {int tmp =  (words[i].size()-1)>>1;rerank(words[i], 0, 0, tmp );if ((words[i].size()&1) != 0) tmp --;rerank(words[i], 1, 0 , tmp);mp[words[i]] = true;}return mp.size();}void rerank(string & w, int p, int be, int en) {if (be >= en) return;char tmp = w[be*2 + p];int oldbe = be, olden = en;while(be < en) {while (be < en && w[be*2 + p] <= tmp) be++;while (oldbe < en && w[en*2 + p] >= tmp) en--;if(be < en) swap(w[be*2 + p], w[en*2 + p]);}swap(w[oldbe*2 + p], w[en*2 + p]);if (oldbe  < en-1) rerank(w, p, oldbe,en-1);if (en+1 < olden) rerank(w, p, en+1, olden);}
};