Leetcode 2901. Longest Unequal Adjacent Groups Subsequence II

本文主要是介绍Leetcode 2901. Longest Unequal Adjacent Groups Subsequence II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• Leetcode 2901. Longest Unequal Adjacent Groups Subsequence II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2901. Longest Unequal Adjacent Groups Subsequence II

1. 解题思路

这一题的题意来说还是要从原始的数组当中选择出一个子串，使得其满足：

1. 相邻两元素group不同；
2. 相邻两元素长度相同但是hamming距离为1；

这就是一个典型的动态规划的题目了，按照每个元素选择与否进行以下考察即可。

2. 代码实现

给出python代码实现如下：

class Solution:def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:@lru_cache(None)def hamming_distance(w1, w2):if len(w1) != len(w2):return -1ans = 0for ch1, ch2 in zip(w1, w2):if ch1 != ch2:ans += 1return ans@lru_cache(None)def dp(idx, prev_group, prev_word):if idx >= n:return []if prev_word == "":ans0 = [words[idx]] + dp(idx+1, groups[idx], words[idx])ans1 = dp(idx+1, 0, "")return ans0 if len(ans0) >= len(ans1) else ans1elif groups[idx] != prev_group and hamming_distance(prev_word, words[idx]) == 1:ans0 = [words[idx]] + dp(idx+1, groups[idx], words[idx])ans1 = dp(idx+1, prev_group, prev_word)return ans0 if len(ans0) >= len(ans1) else ans1else:return dp(idx+1, prev_group, prev_word)return dp(0, 0, "")

提交代码评测得到：耗时3797ms，占用内存312.7MB。

这篇关于Leetcode 2901. Longest Unequal Adjacent Groups Subsequence II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---