2
\$\begingroup\$

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ In the part 1 of this question, I have used num_words(uniq=True) to solve this problem. This is more intuitive than counting number of children. \$\endgroup\$ – coder.in.me Oct 17 '16 at 9:44
  • \$\begingroup\$ @arvindpdmn, I read your code again and sorry I read your code wrong, yes, you are correct uniq=True resolve the problem in a better way. Another question is, for this problem, do you think there are benefit (in terms of algorithm time complexity) using Trie tree (the way you implemented), comparing to other sub-string comparison based solutions like what Joe posted? \$\endgroup\$ – Lin Ma Oct 18 '16 at 4:56
2
\$\begingroup\$
  • 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.

\$\endgroup\$
11
  • \$\begingroup\$ Thanks Joe, two quick questions, (1) from algorithm time complexity perspective, do you think your algorithm is better than Trie tree based algorithm? (2) your method whole_substrings returns only one value, other than a list of possible values, what is the benefit of using yield? I could be wrong, but I remember yield has benefit when multiple values are returned as a list for the caller to enumerate? \$\endgroup\$ – Lin Ma Oct 18 '16 at 4:44
  • 1
    \$\begingroup\$ @LinMa No problem, (1) Without diving too much into it they're roughly the same. My code's a lot faster however. (2) "your method whole_substrings returns only one value" no that's wrong. list(whole_substrings('catcatcatcat')) returns [3, 6, 12]. It means that you can use less memory and delay execution. (3) One way to do this is l=len(word);for i in range(2,int(l**0.5)+1):if l%i==0:yield from [i,l//i]. \$\endgroup\$ – Peilonrayz Oct 18 '16 at 8:15
  • 1
    \$\begingroup\$ @LinMa No int(l ** 0.5) + 1 is a safe bound, if used the same way as above. The 'bug' you're on about is due to the very last line of the function. yield len(word). \$\endgroup\$ – Peilonrayz Oct 19 '16 at 7:49
  • 1
    \$\begingroup\$ @LinMa Yup, that's what I do. Also if you wish to discuss this please start a room between us, :) Comments are not the place. \$\endgroup\$ – Peilonrayz Oct 20 '16 at 7:59
  • 1
    \$\begingroup\$ @LinMa Lets discuss this here \$\endgroup\$ – Peilonrayz Oct 20 '16 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.