671 循环单词

原题网址：http://www.lintcode.com/zh-cn/problem/rotate-words/#

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.

注意事项

所有单词均为小写。

您在真实的面试中是否遇到过这个题？

Yes

样例

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.

 1 class Solution {
 2 public:
 3     /*
 4      * @param words: A list of words
 5      * @return: Return how many different rotate words
 6      */
 7      bool isSame(string s1,string s2)//判断s2是否是s1的子串;
 8 {
 9     if (s1.size()!=s2.size())
10     {
11         return false;
12     }
13     s1=s1+s1;
14     if (s1.find(s2)!=string::npos)
15     {
16         return true;
17     }
18     else
19     {
20         return false;
21     }
22 }
23     int countRotateWords(vector<string> words) {
24         // Write your code here
25         if (words.empty())
26     {
27         return 0;
28     }
29     int size=words.size();
30     bool *isRepeat=new bool[size];
31     memset(isRepeat,false,size); //bool类型一个字节;
32 
33     for (int i=0;i<size;i++)
34     {
35         if (isRepeat[i]==true)
36         {
37             continue;
38         }
39         for (int j=i+1;j<size;j++)
40         {
41             if (isSame(words[i],words[j]))
42             {
43                 isRepeat[j]=true;
44             }
45         }
46     }
47     //统计个数;
48     int count=0;
49     for (int k=0;k<size;k++)
50     {
51         if (!isRepeat[k])
52         {
53             count++;
54         }
55     }
56     return count;
57     }
58 };

参考：

1 https://blog.csdn.net/u013264046/article/details/78358987

2 https://www.cnblogs.com/gousheng/p/7678570.html

3 c/c++学习系列之memset()函数

4 c++ 怎样判断字符串string里面是否含有某个字符串？