After thinking for a long hard time, learning about algorithms to find substrings, and coming to really long and tedious code I decided against my solution and to look for help. The solution was much simpler and elegant. After determining that my code was too much for a simple task I came across an explanation of a simple way to find if one string was a rotation of the other. Man I feel dumb for falling down a long rabbit hole however I learned much about many different things and also how to keep it simple stupid. Previous post of this problem here.

#rotated list

def is_rotated(lst1, lst2):
    ''' Is lst2 a rotation of lst1'''
    str1, str2 = ''.join(map(str,lst1)), ''.join(map(str,lst2))
    if not len(str1) == len(str2):
        raise ValueError("Lengths not equal")

    if str2 in (str1 + str1):
        return True
    return False

# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)

# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)

# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)

# equal
lst2 = lst1
assert is_rotated(lst1, lst2)

# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)


# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)
up vote 3 down vote accepted

Good work! This is certainly primarily an improvement from your previous implementation. However, there are still a few problems.

  1. Don't raise an error when passed two lists of differing length. Not only is this unexpected by users, it breaks some of your tests.

    # 1 empty, 1 not empty
    lst1, lst2 = [], [1]
    assert not is_rotated(lst1, lst2)
    lst1, lst2 = [1], []
    assert not is_rotated(lst1, lst2)
    
  2. The pattern of if condition return True else return False should be replaced with return condition. This is easier to read and reduces the amount of code you have to write!

  3. Joining the lists of integers with the empty string as a separator is dangerous. If I pass in [1, 23] and [12, 3] the function will incorrectly return True. If the function only has to handle integers, you can easily fix this by using a comma (or any other character) as a separator. (Just remember to include it when checking if the string is contained in the other string str1 + ',' + str1)

I would prefer a more general solution that works for lists containing any type of element. Using Nas Banov's answer from Stack Overflow to handle the sub list check, this is a really simple function to write.

def contains_sublist(lst, sublst):
  n = len(sublst)
  return any((sublst == lst[i:i+n]) for i in range(len(lst)-n+1))

def is_rotated(lst1, lst2):
  if not len(lst1) == len(lst2):
    return False
  return len(lst1) == 0 or contains_sublist(lst2 * 2, lst1)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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