【动态规划】【最长子序列】2901. 最长相邻不相等子序列 II

本文涉及知识点

动态规划汇总

最长子序列

LeetCode2901. 最长相邻不相等子序列 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 <= 1000

1 <= words[i].length <= 10

1 <= groups[i] <= n

words 中的字符串 互不相同 。

words[i] 只包含小写英文字母。

动态规划

预处理

words[i]能成为words[j]前面一个元素，则vNeiBo[j].emplace_back(i);

动态规划状态表示

vLen[i] 记录以words[i]结尾的最长子序列，vPreNum[i] 记录此子序列的倒数第二个元素。

状态数：n。

动态规划的状态方程

转移方程的时间复杂度：O(n)，故总时间复杂度：O(nn)

动态规划的初始状态

vPreNum(m_c, -1), vLen(m_c);

动态规划的填表顺序

i从0到words.lenght。

动态规划的返回值

index是vlen最大值的小标，根据vPreNum[index]向前拼接返回值。

代码

class Solution {
public:
  vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
    m_c = words.size();
    vector<vector<int>> vNeiBo(m_c);
    for(int i = 0 ; i < m_c ; i++ )
      for (int j = i + 1; j < m_c; j++)
      {
        if ((groups[i] == groups[j]) || (words[i].size() != words[j].size()))
        {
          continue;
        }
        int iDis = 0;
        for (int k = 0; k < words[i].size(); k++)
        {
          iDis +=( words[i][k] != words[j][k]);
        }
        if (1 != iDis)
        {
          continue;
        }
        vNeiBo[j].emplace_back(i);
      }
    vector<int> vPreNum(m_c, -1), vLen(m_c);
    for (int i = 0; i < m_c; i++)
    {
      int iMaxLen = 0, iMaxIndex = -1;
      for (const auto& j : vNeiBo[i])
      {
        if (vLen[j] > iMaxLen)
        {
          iMaxLen = vLen[j];
          iMaxIndex = j;
        }
      }
      vLen[i] = iMaxLen + 1;
      vPreNum[i] = iMaxIndex;
    }
    int iIndex = std::max_element(vLen.begin(), vLen.end()) - vLen.begin();
    vector<string> vRet;
    while (-1 != iIndex)
    {
      vRet.emplace_back(words[iIndex]);
      iIndex = vPreNum[iIndex];
    }
    return vector<string>(vRet.rbegin(), vRet.rend());
  }
  int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。