class Solution {
public:
vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {
}
};
100077. 最长相邻不相等子序列 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"] 解释：一个可行的子序列是 [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：
输入：n = 4, 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] 只包含小写英文字母。原站题解
golang 解法, 执行用时: 24 ms, 内存消耗: 5 MB, 提交时间: 2023-10-23 00:09:36
func ok(s, t string) (diff bool) {
if len(s) != len(t) {
return
}
for i := range s {
if s[i] != t[i] {
if diff {
return false
}
diff = true
}
}
return
}
func getWordsInLongestSubsequence(n int, words []string, groups []int) []string {
f := make([]int, n)
from := make([]int, n)
mx := n - 1
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if f[j] > f[i] && groups[j] != groups[i] && ok(words[i], words[j]) {
f[i] = f[j]
from[i] = j
}
}
f[i]++ // 加一写在这里
if f[i] > f[mx] {
mx = i
}
}
ans := make([]string, f[mx])
for i := range ans {
ans[i] = words[mx]
mx = from[mx]
}
return ans
}
cpp 解法, 执行用时: 60 ms, 内存消耗: 28 MB, 提交时间: 2023-10-23 00:09:23
class Solution {
bool ok(string &s, string &t) {
if (s.length() != t.length()) {
return false;
}
bool diff = false;
for (int i = 0; i < s.length(); i++) {
if (s[i] != t[i]) {
if (diff) return false;
diff = true;
}
}
return diff;
}
public:
vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {
vector<int> f(n);
vector<int> from(n);
int mx = n - 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (f[j] > f[i] && groups[j] != groups[i] && ok(words[i], words[j])) {
f[i] = f[j];
from[i] = j;
}
}
f[i]++; // 加一写在这里
if (f[i] > f[mx]) {
mx = i;
}
}
int m = f[mx];
vector<string> ans(m);
for (int i = 0; i < m; i++) {
ans[i] = words[mx];
mx = from[mx];
}
return ans;
}
};
java 解法, 执行用时: 31 ms, 内存消耗: 42.4 MB, 提交时间: 2023-10-23 00:09:10
class Solution {
public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
int[] f = new int[n];
int[] from = new int[n];
int mx = n - 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (f[j] > f[i] && groups[j] != groups[i] && ok(words[i], words[j])) {
f[i] = f[j];
from[i] = j;
}
}
f[i]++; // 加一写在这里
if (f[i] > f[mx]) {
mx = i;
}
}
int m = f[mx];
List<String> ans = new ArrayList<>(m);
for (int i = 0; i < m; i++) {
ans.add(words[mx]);
mx = from[mx];
}
return ans;
}
private static boolean ok(String s, String t) {
if (s.length() != t.length()) {
return false;
}
var diff = false;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != t.charAt(i)) {
if (diff) return false;
diff = true;
}
}
return diff;
}
}
python3 解法, 执行用时: 1212 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-23 00:08:54
class Solution:
def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:
def ok(s: str, t: str) -> bool:
return len(s) == len(t) and sum(x != y for x, y in zip(s, t)) == 1
f = [0] * n
from_idx = [0] * n
mx = n - 1
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if f[j] > f[i] and groups[j] != groups[i] and ok(words[i], words[j]):
f[i] = f[j]
from_idx[i] = j
f[i] += 1 # 加一写在这里
if f[i] > f[mx]:
mx = i
ans = [''] * f[mx]
for i in range(f[mx]):
ans[i] = words[mx]
mx = from_idx[mx]
return ans