671. 循环单词重复加标记

The words are same rotate words if rotate the word to the right by loop, and get another. Count how many different rotate word sets in dictionary.

E.g. picture and turepic are same rotate words.

注意事项

所有单词均为小写。 样例 Given dict = ["picture", "turepic", "icturep", "word", "ordw", "lint"] return 3.

"picture", "turepic", "icturep" are same ratote words. "word", "ordw" are same too. "lint" is the third word that different from the previous two words.

重复加标记

难点在于如何判断是否是循环单词，看到别人的思路：可以把当前单词重复一次，然后所有的循环单词都是可以在这个重复的单词中找到的，其实有点像循环移位和线性移位的关系，周期延拓之后线性移位和循环移位的结果是一样的。 比如对于单词word,先重复一遍得到：wordword. word的循环单词都是wordword的子串，找子串可以借助string::find(s)函数，这样就能判断是否是子串。 这样我们就可以去遍历vector中的单词了，对于第一个单词，扩充，然后在余下的单词中找是循环关系的，找到的应该都是要标记出来的，要不会有重复，可以定义一个vector来标记这个单词是否被找到（找到了在后面就无需遍历了），每完成这样的一次查找，计数器+1，一直遍历到最后一个单词。

int countRotateWords(vector<string> words)
     {
        int res = 0;
        int sz = words.size();
        string dbCurrent;
        vector<bool> check(sz, false);
        if (words.empty())
        return res;
        for (int i = 0; i < sz; i++)
        {
        if (!check[i])
        {
            dbCurrent = words[i] + words[i];
            for (int j = i + 1; j < sz; j++)
            {
                if (words[j].size() == words[i].size() && dbCurrent.find(words[j])!=string::npos)
                    check[j] = true;
            }
            res++;
        }
        }
        return res;
     }