資料結構
網路
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 次檢視
廣告