2901. 最長相鄰不相等子序列 II
給你一個整數(shù) n 和一個下標從 0 開始的字符串數(shù)組 words ，和一個下標從 0 開始的數(shù)組 groups ，兩個數(shù)組長度都是 n 。
兩個長度相等字符串的 漢明距離 定義為對應位置字符 不同 的數(shù)目。
你需要從下標 [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 。
請你返回一個字符串數(shù)組，它是下標子序列 依次 對應 words 數(shù)組中的字符串連接形成的字符串數(shù)組。如果有多個答案，返回任意一個。
子序列 指的是從原數(shù)組中刪掉一些（也可能一個也不刪掉）元素，剩余元素不改變相對位置得到的新的數(shù)組。
注意：words 中的字符串長度可能 不相等 。
示例 1：
輸入：n = 3, words = [“bab”,“dab”,“cab”], groups = [1,2,2]
輸出：[“bab”,“cab”]文章來源：http://www.zghlxwxcb.cn/news/detail-718533.html
解題思路
動態(tài)規(guī)劃，唯一路徑文章來源地址http://www.zghlxwxcb.cn/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;
}
}
到了這里，關(guān)于115 雙周賽的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
