2901. 最长相邻不相等子序列 II

给你一个整数 n 和一个下标从 0 开始的字符串数组 words ，和一个下标从 0 开始的数组 groups ，两个数组长度都是 n 。

两个长度相等字符串的 汉明距离 定义为对应位置字符 不同 的数目。

你需要从下标 [0, 1, …, n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i0, i1, …, ik - 1] ，它需要满足以下条件：

相邻 下标对应的 groups 值 不同。即，对于所有满足 0 < j + 1 < k 的 j 都有 groups[ij] != groups[ij + 1] 。
对于所有 0 < j + 1 < k 的下标 j ，都满足 words[ij] 和 words[ij + 1] 的长度 相等 ，且两个字符串之间的 汉明距离 为 1 。
请你返回一个字符串数组，它是下标子序列 依次 对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案，返回任意一个。

子序列 指的是从原数组中删掉一些（也可能一个也不删掉）元素，剩余元素不改变相对位置得到的新的数组。

注意：words 中的字符串长度可能 不相等 。

示例 1：

输入：n = 3, words = [“bab”,“dab”,“cab”], groups = [1,2,2]
输出：[“bab”,“cab”]

解题思路

动态规划，唯一路径

code

class Solution {public Boolean Hamming(String s1,String s2){if(s1.length()!=s2.length())return false;int x = 0;for(int i=0;i<s1.length();i++)if(s1.charAt(i)!=s2.charAt(i)&&++x>1)return false;return true;}public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {int[] source = new int[n];int[] best_seq = new int[n];int max_seq = 0;for(int i=0;i<n;i++){for(int j=i-1;j>=0;j--)if(best_seq[j]>best_seq[i]&&groups[j]!=groups[i]&&Hamming(words[i],words[j])){best_seq[i]=best_seq[j];source[i] = j;}best_seq[i]++;if(best_seq[i]>best_seq[max_seq])max_seq = i;}List<String> result = new ArrayList<>();int now = max_seq;for(int i=0;i<best_seq[max_seq];i++){result.add(words[now]);now = source[now];}for(int i=0;i<result.size()/2;i++)Collections.swap(result, i, result.size()-1-i);return result;}
}