| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
中等 |
1898 |
第 115 场双周赛 Q3 |
|
给你一个整数 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]只包含小写英文字母。
我们定义
另外，我们定义一个变量
我们枚举
最后，我们从
时间复杂度
class Solution:
def getWordsInLongestSubsequence(
self, n: int, 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
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]class Solution {
public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
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;
}
}class Solution {
public:
vector<string> getWordsInLongestSubsequence(int n, 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;
};
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;
}
};func getWordsInLongestSubsequence(n int, 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
}
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
}
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return ans
}function getWordsInLongestSubsequence(n: number, words: string[], groups: number[]): string[] {
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();
}impl Solution {
pub fn get_words_in_longest_subsequence(
n: i32,
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 = n as usize;
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
}
}在方法一中，我们需要枚举所有的
class Solution {
public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
int[] dp = new int[n];
int[] next = new int[n];
Map<String, List<Integer>> strToIdxMap = new HashMap<>();
int maxIdx = n;
for (int i = n - 1; i >= 0; i--) {
int prevIdx = n;
char[] word = words[i].toCharArray();
for (int j = 0; j < word.length; j++) {
// convert word to pattern with '*'.
char temp = word[j];
word[j] = '*';
String curr = new String(word);
// search matches and update dp.
List<Integer> prevList = strToIdxMap.getOrDefault(curr, List.of());
for (int prev : prevList) {
if (groups[prev] == groups[i] || dp[prev] < dp[i]) {
continue;
}
dp[i] = dp[prev] + 1;
prevIdx = prev;
}
// append current pattern to dictionary.
strToIdxMap.computeIfAbsent(curr, k -> new ArrayList<>()).add(i);
// restore pattern to orignal word.
word[j] = temp;
}
if (maxIdx >= n || dp[i] > dp[maxIdx]) {
maxIdx = i;
}
next[i] = prevIdx;
}
int curr = maxIdx;
List<String> ans = new ArrayList<>();
while (curr < n) {
ans.add(words[curr]);
curr = next[curr];
}
return ans;
}
}