diff options
Diffstat (limited to 'longest_unequal_adjacent_group2.py')
-rw-r--r-- | longest_unequal_adjacent_group2.py | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/longest_unequal_adjacent_group2.py b/longest_unequal_adjacent_group2.py new file mode 100644 index 0000000..44255d1 --- /dev/null +++ b/longest_unequal_adjacent_group2.py @@ -0,0 +1,50 @@ +# 2901. Longest Unequal Adjacent Groups Subsequence II + +""" +you are given a string array 'words' and an array 'groups', both arrays +having length 'n'. the hamming distance between two strings of equal length +is the number of positions at which the corresponding characters are +different. you need to select the longest subsequence from an array of +indices such that for the subsequence denoted as '[i0, i1, ..., ik-1]' having +length 'k', the following holds true: for adjacent indices in the subsequence +their corresponding groups are unequal. 'words[i]' and 'words[i + 1]' are +equal in length and the haming distance between them is 1. return a string +array containing the words corresponding to the indices in order in the +selected subsequence. if there are multiple, return any of them. +""" + + +class Solution(object): + def getWordsInLongestSubsequence(self, words, groups): + """ + :type words: List[str] + :type groups: List[int] + :rtype: List[str] + """ + dp = [] + for i, j in zip(words, groups): + dp.append( + max( + ( + k + for a, b, k in zip(words, groups, dp) + if j != b and len(i) == len(a) and sum(map(ne, i, a)) < 2 + ), + key=len, + default=[], + ) + + [i] + ) + return max(dp, key=len) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.getWordsInLongestSubsequence(words=["bab", "dab", "cab"], groups=[1, 2, 2]) + ) + print( + obj.getWordsInLongestSubsequence( + words=["a", "b", "c", "d"], groups=[1, 2, 3, 4] + ) + ) |