力扣-2904最短且字典序最小的美丽子序列

简介: 力扣-2904最短且字典序最小的美丽子序列

给你一个二进制字符串 s 和一个正整数 k 。

如果 s 的某个子字符串中 1 的个数恰好等于 k ,则称这个子字符串是一个 美丽子字符串 。

令 len 等于 最短 美丽子字符串的长度。

返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串,则返回一个 空 字符串。

对于相同长度的两个字符串 a 和 b ,如果在 a 和 b 出现不同的第一个位置上,a 中该位置上的字符严格大于 b 中的对应字符,则认为字符串 a 字典序 大于 字符串 b 。

  • 例如,"abcd" 的字典序大于 "abcc" ,因为两个字符串出现不同的第一个位置对应第四个字符,而 d 大于 c 。

示例 1:

输入:s = "100011001", k = 3AA

输出:"11001"

解释:示例中共有 7 个美丽子字符串:

1. 子字符串 "100011001" 。

2. 子字符串 "100011001" 。

3. 子字符串 "100011001" 。

4. 子字符串 "100011001" 。

5. 子字符串 "100011001" 。

6. 子字符串 "100011001" 。

7. 子字符串 "100011001" 。

最短美丽子字符串的长度是 5 。

长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。

示例 2:

输入:s = "1011", k = 2

输出:"11"

解释:示例中共有 3 个美丽子字符串:

1. 子字符串 "1011" 。

2. 子字符串 "1011" 。

3. 子字符串 "1011" 。

最短美丽子字符串的长度是 2 。

长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。

例 3

输入:s = "000", k = 1

输出:""

解释:示例中不存在美丽子字符串。

提示:

  • 1 <= s.length <= 100
  • 1 <= k <= s.length

分析问题:

       由题意知,s是由0,1组成的字符串,要在这个长字符串里面找子序列,使得该子序列里面1的个数等于k,那么首先我们要排除k大于s中所有1的个数,这时候直接return空字符串,否则我们去找所有的1,最美子序列的第一个数字一定是1,那么就可以进行s.count('1')-n+1个循环,去遍历所有的可能性,起始值是s中第一个1的下标,遍历过去就把这个1变成0,以便我们继续使用index函数。把所有可能性放进列表里面,筛选出长度最短的最美子序列以int类型放入另一个列表里面,方便我们进行比大小。然后输出最小的最短最美子序列,注意输出要求是字符串类型,还需将其转为str类型输出。

代码实现:

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        v=''
        if s.count('1') <k: return v
        n=len(s)
        a_min=101 # 最小长度
        dp=[0]*(n+5)
        ls=[]
        for q in range(n):
            if s[q]=='1':
                dp[q]=1
        b=dp.count(1)
        for i in range(b-k+1):
            a=dp.index(1)+1
            kk=a-1
            v='1'
            l=1
            while l<k:
                if dp[a]==1:
                    v+='1'
                    l+=1
                else: v+='0'
                a+=1
            dp[kk]=0
            if len(v)<=a_min: 
                a_min=len(v)
                ls.append(v)
        last=len(ls[-1])
        li=[]
        for w in ls:
            if len(w)==last: li.append(int(w))
        if len(li)==1: return str(li[0])
        return str(min(li))

总结:      

       首先对字符串 s 进行遍历,统计字符串 s 中 1 的数量并将结果存储在 dp 数组中。然后从 dp 数组中找出第一个出现 1 的位置,并依次向后构建长度为 k 的子串,判断子串的长度是否小于当前已找到的最小长度。如果是,则更新最小长度,并将当前子串长度和子串本身存储下来。最后对符合条件的子串进行筛选,返回最小的子串。

相关文章
|
2月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
2月前
代码随想录 Day46 动态规划14 LeetCode T392 判断子序列 T115 不同的子序列
代码随想录 Day46 动态规划14 LeetCode T392 判断子序列 T115 不同的子序列
46 0
|
2月前
|
算法 Java
[Java·算法·简单] LeetCode 392. 判断子序列 详细解读
[Java·算法·简单] LeetCode 392. 判断子序列 详细解读
52 0
|
21天前
|
算法 测试技术 程序员
力扣经典150题第三十题:长度最小的子数组
力扣经典150题第三十题:长度最小的子数组
10 1
|
1月前
|
机器学习/深度学习 存储 算法
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
|
1月前
|
存储 自然语言处理 算法
LeetCode题目115:不同子序列
LeetCode题目115:不同子序列
|
21天前
|
算法 索引
力扣经典150题第二十六题:判断子序列
力扣经典150题第二十六题:判断子序列
9 0
|
2月前
|
人工智能
力扣100114. 元素和最小的山形三元组 II(中等)
力扣100114. 元素和最小的山形三元组 II(中等)
|
1月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
|
1月前
|
存储 机器学习/深度学习 算法
python 3种算法 回溯法、字典序生成、递归交换 实现全排列【力扣46题】
python 3种算法 回溯法、字典序生成、递归交换 实现全排列【力扣46题】