本文主要是介绍LC2014-重复k次的最长子序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2014. 重复 K 次的最长子序列
- 统计s中每个字符出现频率
cnt
,获得频率大于等于k的字符,答案只会由这些字符组成,因此dfs全排列再check该排列是否符合出现k次这一条件
- 为了保证字典序,将chs逆序存储,并从大到小枚举字符串长度,遇到符合即返回答案
class Solution {
public:
string s; int k;
bool check(string &t){
int cnt = 0;
for(int i = 0, j = 0; i < s.size(); ++i){
if(s[i] == t[j]) j++;
if(j == t.size()) j = 0, cnt ++;
}
return cnt >= k;
}
bool dfs(vector<char> &chs, const int len, string &t, int used){
if(t.size() == len){
if(check(t)) return true;
return false;
}
for(int i = 0; i < chs.size(); ++i){
if(!(used >> i & 1)){
t.push_back(chs[i]);
if(dfs(chs, len, t, used | (1 << i))) return true;
t.pop_back();
}
}
return false;
}
string longestSubsequenceRepeatedK(string _s, int _k) {
s = _s, k = _k;
vector<int>cnt(26);
vector<char>chs;
for(auto x : s) ++cnt[x - 'a'];
for(int i = 25; i >= 0; --i) //get 频率大于k的字符 倒序排序
while(cnt[i] / k){
chs.push_back(i + 'a');
cnt[i] -= k;
}
for(int len = chs.size(); len >= 1; --len){ // 枚举长度
string t = "";
if(dfs(chs,len,t,0)) return t;
}
return "";
}
};
这篇关于LC2014-重复k次的最长子序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!