数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的最长字符串链
假设我们有一系列单词，每个单词都由小写字母组成。因此，一个单词 word1 是另一个单词 word2 的前驱，当且仅当我们可以在 word1 中的任意位置添加一个字母使其等于 word2。例如，“abc”是“abac”的前驱。现在，一个单词链是一系列单词[word_1, word_2, ..., word_k]，其中 k >= 1，且 word_1 是 word_2 的前驱，word_2 是 word_3 的前驱，依此类推。我们需要找到从给定单词列表中选择的单词的最长可能的单词链长度。
例如，如果输入为：["a","b","ba","bca","bda","bdca"]，则结果为 4，因为其中一个最长的链将是 [“a”, “ba”, “bda”, “bdca”]。
为了解决这个问题，我们将遵循以下步骤：
定义一个映射 dp，n := words 数组的大小
根据长度对 words 数组进行排序
ret := 0
对于 i 的范围从 0 到 n – 1
best := 0
对于 j 的范围从 0 到 word[i] 的长度 – 1
word := (words[i] 从 0 到 j – 1 的子字符串) 连接 (words[i] 从 j + 1 到末尾的子字符串)
best := best 和 dp[word] + 1 的最大值
dp[words[i]] := best
ret := (ret 和 dp[words[i]]) 的最大值
返回 ret
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(string s1, string s2){
return s1.size() < s2.size();
}
int longestStrChain(vector<string>& words) {
unordered_map <string, int> dp;
int n = words.size();
sort(words.begin(), words.end(), cmp);
int ret = 0;
for(int i = 0; i < n; i++){
int best = 0;
for(int j = 0; j < words[i].size(); j++){
string word = words[i].substr(0, j) +
words[i].substr(j + 1);
best = max(best, dp[word] + 1);
}
dp[words[i]] = best;
ret = max(ret, dp[words[i]]);
}
return ret;
}
};
main(){
vector<string> v = {"a","b","ba","bca","bda","bdca"};
Solution ob;
cout << (ob.longestStrChain(v));
}输入
["a","b","ba","bca","bda","bdca"]
输出
4
更新于: 2020年4月30日
464 次查看
广告