115 双周赛

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39