2901. 最长相邻不相等子序列 II
题目描述
给定一个字符串数组 words ，和一个数组 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：
输入：words = ["bab","dab","cab"], groups = [1,2,2] 输出：["bab","cab"] 解释：一个可行的子序列是 [0,2] 。 - groups[0] != groups[2] - words[0].length == words[2].length 且它们之间的汉明距离为 1 。 所以一个可行的答案是 [words[0],words[2]] = ["bab","cab"] 。 另一个可行的子序列是 [0,1] 。 - groups[0] != groups[1] - words[0].length = words[1].length 且它们之间的汉明距离为 1 。 所以另一个可行的答案是 [words[0],words[1]] = ["bab","dab"] 。 符合题意的最长子序列的长度为 2 。
示例 2：
输入：words = ["a","b","c","d"], groups = [1,2,3,4] 输出：["a","b","c","d"] 解释：我们选择子序列 [0,1,2,3] 。 它同时满足两个条件。 所以答案为 [words[0],words[1],words[2],words[3]] = ["a","b","c","d"] 。 它是所有下标子序列里最长且满足所有条件的。 所以它是唯一的答案。
提示：
1 <= n == words.length == groups.length <= 10001 <= words[i].length <= 101 <= groups[i] <= nwords中的字符串 互不相同 。words[i]只包含小写英文字母。
解法
方法一：动态规划
我们定义 $f[i]$ 表示以第 $i$ 个单词结尾的最长相邻不相等子序列的长度，定义 $g[i]$ 表示以第 $i$ 个单词结尾的最长相邻不相等子序列的前驱下标。初始时 $f[i] = 1$, $g[i] = -1$。
另外，我们定义一个变量 $mx$ 表示最长相邻不相等子序列的长度。
我们枚举 $i$，枚举 $j \in [0, i)$，如果 $groups[i] \neq groups[j]$ 且 $f[i] \lt f[j] + 1$ 且 $words[i]$ 和 $words[j]$ 之间的汉明距离为 $1$，则更新 $f[i] = f[j] + 1$，$g[i] = j$，并且更新 $mx = \max(mx, f[i])$。
最后，我们从 $f$ 数组中找到最大值对应的下标 $i$，然后从 $i$ 开始不断往前找，直到找到 $g[i] = -1$，这样就找到了最长相邻不相等子序列。
时间复杂度 $O(n^2 \times L)$，空间复杂度 $O(n)$。其中 $L$ 表示单词的最大长度。
Python3
class Solution:
def getWordsInLongestSubsequence(
self, words: List[str], groups: List[int]
) -> List[str]:
def check(s: str, t: str) -> bool:
return len(s) == len(t) and sum(a != b for a, b in zip(s, t)) == 1
n = len(groups)
f = [1] * n
g = [-1] * n
mx = 1
for i, x in enumerate(groups):
for j, y in enumerate(groups[:i]):
if x != y and f[i] < f[j] + 1 and check(words[i], words[j]):
f[i] = f[j] + 1
g[i] = j
mx = max(mx, f[i])
ans = []
for i in range(n):
if f[i] == mx:
j = i
while j >= 0:
ans.append(words[j])
j = g[j]
break
return ans[::-1]
Java
class Solution {
public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
int n = groups.length;
int[] f = new int[n];
int[] g = new int[n];
Arrays.fill(f, 1);
Arrays.fill(g, -1);
int mx = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (groups[i] != groups[j] && f[i] < f[j] + 1 && check(words[i], words[j])) {
f[i] = f[j] + 1;
g[i] = j;
mx = Math.max(mx, f[i]);
}
}
}
List<String> ans = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (f[i] == mx) {
for (int j = i; j >= 0; j = g[j]) {
ans.add(words[j]);
}
break;
}
}
Collections.reverse(ans);
return ans;
}
private boolean check(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int cnt = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) != t.charAt(i)) {
++cnt;
}
}
return cnt == 1;
}
}
C++
class Solution {
public:
vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
auto check = [](string& s, string& t) {
if (s.size() != t.size()) {
return false;
}
int cnt = 0;
for (int i = 0; i < s.size(); ++i) {
cnt += s[i] != t[i];
}
return cnt == 1;
};
int n = groups.size();
vector<int> f(n, 1);
vector<int> g(n, -1);
int mx = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (groups[i] != groups[j] && f[i] < f[j] + 1 && check(words[i], words[j])) {
f[i] = f[j] + 1;
g[i] = j;
mx = max(mx, f[i]);
}
}
}
vector<string> ans;
for (int i = 0; i < n; ++i) {
if (f[i] == mx) {
for (int j = i; ~j; j = g[j]) {
ans.emplace_back(words[j]);
}
break;
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};
Go
func getWordsInLongestSubsequence(words []string, groups []int) []string {
check := func(s, t string) bool {
if len(s) != len(t) {
return false
}
cnt := 0
for i := range s {
if s[i] != t[i] {
cnt++
}
}
return cnt == 1
}
n := len(groups)
f := make([]int, n)
g := make([]int, n)
for i := range f {
f[i] = 1
g[i] = -1
}
mx := 1
for i, x := range groups {
for j, y := range groups[:i] {
if x != y && f[i] < f[j]+1 && check(words[i], words[j]) {
f[i] = f[j] + 1
g[i] = j
if mx < f[i] {
mx = f[i]
}
}
}
}
ans := make([]string, 0, mx)
for i, x := range f {
if x == mx {
for j := i; j >= 0; j = g[j] {
ans = append(ans, words[j])
}
break
}
}
slices.Reverse(ans)
return ans
}
TypeScript
function getWordsInLongestSubsequence(words: string[], groups: number[]): string[] {
const n = groups.length;
const f: number[] = Array(n).fill(1);
const g: number[] = Array(n).fill(-1);
let mx = 1;
const check = (s: string, t: string) => {
if (s.length !== t.length) {
return false;
}
let cnt = 0;
for (let i = 0; i < s.length; ++i) {
if (s[i] !== t[i]) {
++cnt;
}
}
return cnt === 1;
};
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (groups[i] !== groups[j] && f[i] < f[j] + 1 && check(words[i], words[j])) {
f[i] = f[j] + 1;
g[i] = j;
mx = Math.max(mx, f[i]);
}
}
}
const ans: string[] = [];
for (let i = 0; i < n; ++i) {
if (f[i] === mx) {
for (let j = i; ~j; j = g[j]) {
ans.push(words[j]);
}
break;
}
}
return ans.reverse();
}
Rust
impl Solution {
pub fn get_words_in_longest_subsequence(words: Vec<String>, groups: Vec<i32>) -> Vec<String> {
fn check(s: &str, t: &str) -> bool {
s.len() == t.len() && s.chars().zip(t.chars()).filter(|(a, b)| a != b).count() == 1
}
let n = groups.len();
let mut f = vec![1; n];
let mut g = vec![-1; n];
let mut mx = 1;
for i in 0..n {
let x = groups[i] as usize;
for j in 0..i {
let y = groups[j] as usize;
if x != y && f[i] < f[j] + 1 && check(&words[i], &words[j]) {
f[i] = f[j] + 1;
g[i] = j as i32;
mx = mx.max(f[i]);
}
}
}
let mut ans = vec![];
let mut i = n - 1;
while f[i] != mx {
i -= 1;
}
let mut j = i as i32;
while j >= 0 {
ans.push(words[j as usize].clone());
j = g[j as usize];
}
ans.reverse();
ans
}
}