Leetcode 522 Solution

This article provides solution to leetcode question 522 (longest-uncommon-subsequence-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 522" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/longest-uncommon-subsequence-ii

Solution

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def is_sub_seq(A, B):
            if len(A) > len(B):
                return False

            i = 0
            j = 0
            while i < len(A) and j < len(B):
                if A[i] == B[j]:
                    i += 1
                j += 1
            return i == len(A)

        str_pairs = sorted([
            (-len(s), s) for s in strs
        ])

        for i, (_, s) in enumerate(str_pairs):
            valid = True
            for j in range(0, len(str_pairs)):
                if i != j and is_sub_seq(s, str_pairs[j][1]):
                    valid = False
                    break
            if valid:
                return len(s)

        return -1