LeetCode算法心得——最短且字典序最小的美丽子字符串（枚举的思想）

大家好，我是晴天学长，暴力枚举，其中的字符串的字典序的比较尤其做笔记哦，需要的小伙伴可以关注支持一下哦！后续会继续更新的。

---

---

1) . 最短且字典序最小的美丽子字符串

---

最短且字典序最小的美丽子字符串

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

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

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

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

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

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

示例 1：

输入：s = "100011001", k = 3
输出："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

---

2) .算法思路

最短且字典序最小的美丽子字符串

1.首先确定字符串的1够不够k
用取代的方法（“”）
2.开始枚举字符串
先是字符串的长度
然后是字符串的位置
3.判断是否符合要求，并替换答案。

---

3) .算法步骤

1.首先，通过判断字符串 s 中非零字符的数量是否小于 k，如果是，则直接返回空字符串 “”，因为无法找到满足条2.件的美丽子串。
3.接下来，通过一个循环来不断增加子串的长度 size。
4.在每个循环迭代中，初始化一个空字符串 ans 用于记录满足条件的美丽子串。
5.在内层循环中，从索引 i=size 开始遍历字符串 s，以长度为 size 的子串 t 进行处理。
6.判断 t 是否满足以下条件：
7.ans 为空或 t 字典序比 ans 小，并且 t 中非零字符的数量等于 k，即满足美丽子串的要求。
8.如果满足条件，则更新 ans 为当前子串 t。
9.继续遍历，直到遍历完整个字符串 s。
10.如果 ans 非空，则找到了满足条件的美丽子串，直接返回 ans。
11.如果 ans 仍然为空，则继续增加子串的长度 size，继续循环查找，直到找到满足条件的美丽子串或者字符串已经遍历完毕。

---

4）.代码示例

方法一：枚举

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
         if (s.replace("0", "").length() < k) {
                return "";
            }

            for (int size = k; ;size++) {
                String ans = "";
                // 可以避免越界。
                for (int i = size; i <= s.length(); i++) {
                    String t = "";
                    t = s.substring(i - size, i);
                    if ((ans.isEmpty() || t.compareTo(ans) < 0) && t.replace("0", "").length() == k) {
                        ans = t;
                    }
                }
                if (!ans.isEmpty()) {
                    return ans;
                }
            }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二：
1.首先，通过判断字符串 s 中非零字符的数量是否小于 k，如果是，则直接返回空字符串 “”，因为无法找到满足条2.件的美丽子串。
3.初始化一个空字符串 ans 用于记录满足条件的最短美丽子串。
4.初始化左指针 left 为 0，表示滑动窗口的左边界。
5.初始化右指针 right 为字符串 s 中第一个出现的字符 ‘1’ 的索引，表示滑动窗口的右边界。
6.通过一个循环来遍历字符串 s，从右指针 right 开始：
7.构造当前子串 t，即从左指针 left 到右指针 right 的子串。
8.当 t 中非零字符的数量大于 k 或者左边界的字符为 ‘0’ 时，收缩窗口，即将左指针 left 向右移动，并更新子串 t。
9.如果 t 中非零字符的数量等于 k，则满足美丽子串的要求，判断是否更新 ans：
10如果 ans 为空，或者 t 的长度小于 ans 的长度，或者 t 的长度等于 ans 的长度但 t 字典序比 ans 小，则更新 ans 为当前子串 t。
11.返回最终的满足条件的美丽子串 ans。

class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
         if (s.replace("0", "").length() < k) {
                return "";
            }
            String ans = "";
            int left = 0;
            int n = s.length();
            for (int right = s.indexOf('1'); right < n; right++) {
                String t = s.substring(left, right + 1);
                while (t.replace("0", "").length() > k || s.charAt(left) == '0') {
                    left++;
                    t = s.substring(left, right + 1);
                }
                if (t.replace("0", "").length() == k) {
                    t = s.substring(left, right + 1);
                    if (ans.isEmpty() || t.length() < ans.length() || t.length() == ans.length() && t.compareTo(ans) < 0) {
                        ans = t;
                    }
                }
            }
            return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

5）.总结

• 字典序的比较。

---

试题链接：