[LintCode 671] Rotate Words | DataLeoZ | 数据里奥斯

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.

如果一个单词通过循环右移获得的单词，我们称这些单词都为一种循环单词。 现在给出一个单词集合，需要统计这个集合中有多少种不同的循环单词。

例如：picture 和 turepic 就是属于同一种循环单词。

https://www.lintcode.com/problem/rotate-words/description

Example:

Input : ["picture", "turepic", "icturep", "word", "ordw", "lint"]
Output : 3
Explanation : 
"picture", "turepic", "icturep" are same ratote words.
"word", "ordw" are same too.
"lint" is the third word that different from the previous two words.

Note

最直接的方法是使用两层loop检查并解决，但是在数组巨大时N2会超时，于是想到此处只需要知道有多少种不一样的word，所以通过set记录即可，要利用set中的in属性，此类查询是常数时间，而将某一单词枚举所有可能的旋转情况次数会远小于set中单词个数，所以只需要用当前单词枚举和set中进行比对就可以有效降低复杂度

Update Review

Code

Python3 on LintCode

Original Solution

class Solution:
    """
    @param: words: A list of words
    @return: Return how many different rotate words
    """
    def countRotateWords(self, words):
        # Write your code here
        # this methods use 2 loop when words is too large it can sceed time limit
        counts = set()
        for word in words:
            is_checked = False
            for count in counts:
                check = count + count
                if check.find(word) != -1 and len(word) == len(count):
                    is_checked = True
                    break
            if not is_checked:
                counts.add(word)
        return len(counts)

Optimized Solution

class Solution:
    """
    @param: words: A list of words
    @return: Return how many different rotate words
    """
    def countRotateWords(self, words):        
        counts = set()
        for word in words:
            tmp = word + word
            is_checked = False
            for i in range(0,len(word)):
                if tmp[i: i + len(word)] in counts:
                    is_checked = True
                    break
            if not is_checked:
                counts.add(word)

        return len(counts)

Ref Code

本参考程序来自九章算法，由 @令狐冲 提供

思路类似，但是答案中是如果重复就在集合中删除，而我自己的做法是如果确认不重复再添加，操作次数有所降低，但是依然还是在一个复杂度级别

class Solution:
    """
    @param: words: A list of words
    @return: Return how many different rotate words
    """
    def countRotateWords(self, words):
        # Write your code here
        dict = set()
        for w in words:
            s = w + w
            print s
            for i in range(0, len(w)):
                tmp = s[i : i +len(w)]
                if tmp in dict:
                    dict.remove(tmp)
            dict.add(w)
        return len(dict)

This blog is under a CC BY-NC-SA 3.0 Unported License
本文使用 CC BY-NC-SA 3.0 中国 协议许可
署名-非商业性使用-相同方式共享（BY-NC-SA）：使用者可以对本创作进行共享、演绎，但使用时须进行署名（同时标明是否（对原始作品）作了修改），且不得运用于商业目的，采用本创作的内容必须同样采用本协议进行授权。详情请参考协议细则。
本文链接：https://dataleoz.com/lintcode-rotate-words/