原题

LintCode 671. Rotate Words

Description

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.

Notice

All words are lowercase.

Example

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.

解题

题意为统计一个数组中所有不同的字符串的个数。如果两个字符串可以通过旋转的方式得到彼此，则认为这两个字符串是相同的。

主要是如何判断两个字符串是否可以通过旋转得到彼此。一个简单的方法是，将一个字符串重复两边，即str = str + str，此时如果能从str中找到另一个字符串，则可以判断str可以通过旋转获得另一个字符串。

代码

class Solution {
public:
    /*
    * @param words: A list of words
    * @return: Return how many different rotate words
    */
    int countRotateWords(vector<string> words) {
        // Write your code here
        if (words.empty()) return 0;
        vector<string> ans;
        auto it = words.begin();
        ans.push_back(*it++);
        while (it != words.end()) {
            bool hasPer = any_of(ans.begin(), ans.end(), [&it](string& str) {
                if (it->length() != str.length()) return false;
                string temp = str + str;
                return temp.find(*it) != -1;
            });
            if (!hasPer) ans.push_back(*it);
            it++;
        }
        return ans.size();
    }
};