本文主要是介绍Leetcode1839. 所有元音按顺序排布的最长子字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Every day a Leetcode
题目来源:1839. 所有元音按顺序排布的最长子字符串
解法1:滑动窗口
要找的是最长美丽子字符串的长度,我们可以用滑动窗口解决。
设窗口内的子字符串为 window,每当 word[right] >= window.back() 时,说明可以按字典序升序排布,我们都可以将 word[right] 添加进 window 的末尾,我们使用一个集合 cnt 存储每次遇到的 word[right],当 cnt.size() = 5时,说明所有 5 个英文元音字母都至少出现了一次,更新长度:max_len = max(max_len, (int)window.size())。
如果遇到了不按字典序升序排布的情况,我们发现窗口必须全部清空,于是有:window = “”,cnt.clear(),同时要改变窗口的左边界 left = right,立即将 word[left] 加入进窗口和集合,重新开始遍历。
代码:
/** @lc app=leetcode.cn id=1839 lang=cpp** [1839] 所有元音按顺序排布的最长子字符串*/// @lc code=start// 滑动窗口class Solution
{
public:int longestBeautifulSubstring(string word){// 特判if (word.size() < 5)return 0;int n = word.size();string window;unordered_set<char> cnt;int max_len = 0, left = 0, right = 0;while (right < n){if (window.empty() || word[right] >= window.back()){window += word[right];cnt.insert(word[right]);right++;if (cnt.size() == 5)max_len = max(max_len, (int)window.size());}else{window = "";cnt.clear();left = right;window += word[left];cnt.insert(word[left]);right++;}}return max_len;}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n),其中 n 是字符串 word 的长度。
空间复杂度:O(n),其中 n 是字符串 word 的长度。
解法2:一次遍历
由滑动窗口的启发,我们发现只设立几个变量也能达到相同的效果。
代码:
class Solution
{
public:int longestBeautifulSubstring(string word){// 特判if (word.size() < 5)return 0;int n = word.size();int max_len = 0;int vowel = 1, cur_len = 1;for (int i = 1; i < n; i++){if (word[i] >= word[i - 1]){cur_len++;if (word[i] > word[i - 1])vowel++;}else{cur_len = 1;vowel = 1;}if (vowel == 5)max_len = max(max_len, cur_len);}return max_len;}
};
结果:
复杂度分析:
时间复杂度:O(n),其中 n 是字符串 word 的长度。
空间复杂度:O(1)。
这篇关于Leetcode1839. 所有元音按顺序排布的最长子字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!