Find the shortest whole repetitive substring (part 2)

Question

This is a continued improvement from discussion here (Find the shortest whole repetitive substring), since code has changed a lot dues to improvement, I post it here. Major smart ideas are from arvindpdmn.

Major algorithm ideas,

1. since we need to find wholly repetitive sub-strings, we only build Trie tree if the sub-string length is a factor of total string length (if not a factor, such sub-string are not eligible dues to not able to wholly repetitive)
2. If wholly repetitive, all nodes need to have only one child node. I did the checking in method checkChildNumber.

Questions,

Trie tree is the best way I can think of to resolve this problem for the purpose of reducing algorithm time complexity, not sure if any other better ideas to make it even faster (in terms of algorithm time complexity perspective).

from __future__ import print_function
from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.isEnd = False
    def addNode(self, word):
        node = self
        for ch in word:
            node = node.children[ch]
        node.isEnd = True
    def checkChildNumber(self):
        node = self
        while node.isEnd == False:
            if len(node.children) != 1:
                return False
            for child in node.children.values():
                node = child
        return True

if __name__ == "__main__":
    word = "catcatcat" # output is 3
    #word = "aaaaaaa" # output is 1
    #word = "aaaaaab" # output is 7
    result = len(word)
    for subLength in range(1, len(word)//2 + 1):
        if len(word) % subLength == 0:
            start = 0
            root = TrieNode()
            while start <= len(word) - subLength:
                root.addNode(word[start:start+subLength])
                start += subLength
            if root.checkChildNumber():
                result = min(result, subLength)

    print (result)

Answer 1

• You don't follow PEP8's naming conventions, which makes your code slightly harder to read for those used to it.
• You should use is when comparing to booleans. Or you can remove the comparison and use not. Which reads better, while not node.isEnd.
• While loops are normally better written as for loops. As then you don't have to define a variable outside it's scope, and then increment it in the loop.
• Using a trie is a bit much here. It makes the code more complex for no measurable improvement to the code.

Instead I'd change your code to just be the code in you __name__ == '__main__'. This is as it's the part that's doing most of the work.

Keeping the outer for loop, and the if. You can change the while loop to be a generator of substrings, and then you compare all slices to the first slice, and if they are all the same yield the size. If any of them are not go to the next sub-length.

def whole_substrings(word):
    for sub_length in range(1, len(word) // 2 + 1):
        if len(word) % sub_length == 0:
            sub_slices = (
                word[start:start+sub_length]
                for start in range(0, len(word), sub_length)
            )
            first = next(sub_slices, None)
            for i in sub_slices:
                if i != first:
                    break
            else:
                yield sub_length
    yield len(word)

You can use this in two ways the less cryptic min, or the more cryptic next. As it guarantees the items are returned in sorted order.

To further improve this you can change the for sub-length loop to be \$O(\sqrt{n})\$, rather than \$O(n)\$. If you yield the product and the 'other half' of the product, i.e. 3 * 5 == 15, so you'd yield 3 and 5, by just by finding 3.