Leetcode 串联字符串的最大长度
2021/10/16 6:15:54
本文主要是介绍Leetcode 串联字符串的最大长度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
串联字符串的最大长度
给定一个字符串数组 arr,字符串 s 是将 arr 某一子序列字符串连接所得的字符串,如果 s 中的每一个字符都只出现过一次,那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
示例 1:
输入:arr = ["un","iq","ue"] 输出:4 解释:所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique",最大长度为 4。
示例 2:
输入:arr = ["cha","r","act","ers"] 输出:6 解释:可能的解答有 "chaers" 和 "acters"。
示例 3:
输入:arr = ["abcdefghijklmnopqrstuvwxyz"] 输出:26
提示:
- 1 <= arr.length <= 16
- 1 <= arr[i].length <= 26
- arr[i] 中只含有小写英文字
这一道题我们是要求解最大长度,关键是不能出现重复的字母。解决方法我看了答案有很多种,用位运算。这个方法我一开始没有想到。我想到的方法是之间用过的回溯算法。怎么判断是否重复呢?我在这里采用的是哈希表unordered_set
。为了更方便的使用回溯算法,这里我们用vector<string>
来分别储存字符串(需要保留顺序,因为先要push_back, 结束后要pop_back),关键是我们怎么确定退出条件。以下是实现代码。
思路:回溯算法
class Solution { public: //计算长度 int clac_length(vector<string> & arr){ string s; if(arr.empty()) return 0; for(int i=0;i<arr.size();i++){ s = s + arr[i]; } int length = s.size(); return length; } //判断字符串是否重复 bool isRepeat(vector<string> & arr){ unordered_set<char> a; string s; if(arr.empty()){ return false; } for(int i=0;i<arr.size();i++){ s = s + arr[i]; } for(char i:s){ a.insert(i); } if(a.size()==s.size()) return false; return true; } //dfs 深度优先遍历 void dfs(int begin, int& max, vector<string>& arr, vector<string>& ans,int& step){ if(isRepeat(ans)) return; int length = clac_length(ans); if(length>max) max = length; if(begin==arr.size()){ return; } for(int i=begin;i<arr.size();++i){ ans.push_back(arr[i]); dfs(i+1, max, arr, ans, step); ans.pop_back(); } } int maxLength(vector<string>& arr) { vector<string> ans; int max = 0; int step = 1; dfs(0, max, arr, ans, step); return max; } };
这篇关于Leetcode 串联字符串的最大长度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain