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”]文章来源:https://www.toymoban.com/news/detail-718533.html
解题思路
动态规划,唯一路径文章来源地址https://www.toymoban.com/news/detail-718533.html
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;
}
}
到了这里,关于115 双周赛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!