【贪心难题】力扣1585-检查字符串是否可以通过排序子字符串得到另一个字符串

摘要: 贪心

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我们来看一个贪心的问题。这是第 206 场周赛 D 题，是限制操作方式的数组重排的场景。

$1 题目

• 1585. 检查字符串是否可以通过排序子字符串得到另一个字符串

给你两个字符串 s 和 t ，请你通过若干次以下操作将字符串 s 转化成字符串 t ：

• 选择 s 中一个 非空 子字符串并将它包含的字符就地 升序 排序。

比方说，对下划线所示的子字符串进行操作可以由 “14234” 得到 “12344” 。

如果可以将字符串 s 变成 t ，返回 true 。否则，返回 false 。

一个 子字符串 定义为一个字符串中连续的若干字符。

提示：

s.length == t.length
1 <= s.length <= 105
s 和 t 都只包含数字字符，即 '0' 到 '9' 。

示例 1：
输入：s = “84532”, t = “34852”
输出：true
解释：你可以按以下操作将 s 转变为 t ：
“84532” （从下标 2 到下标 3）-> “84352”
“84352” （从下标 0 到下标 2） -> “34852”

示例 2：
输入：s = “34521”, t = “23415”
输出：true
解释：你可以按以下操作将 s 转变为 t ：
“34521” -> “23451”
“23451” -> “23415”

示例 3：
输入：s = “12345”, t = “12435”
输出：false

示例 4：
输入：s = “1”, t = “2”
输出：false

$2 题解

算法: 贪心

用一下结构记录 0~9 各个数字从小到大的下标：

vector<list<int>> cnts(10);

贪心的算法流程如下：

枚举 `i = 1..n-1`，当前考察的数字为 `cur = t[i]`:
    若要最终 s = t，要么此时已经 `s[i] == t[i]`，要么需要有某个位置 j，`s[j] = t[i]`，并且 `s[j]` 按照冒泡排序的规则可以交换到 s[i]。
    判断 s[j] 可否交换到 s[i] 时，只需要判断使得 `s[j] = t[i]` 的最小的 j 即可(**贪心**)
    判断 s[j] 可否交换到 s[i]: 枚举所有比 cur 小的数字，如果其下标集合非空并且最小的下标小于 j 则返回 false
    当 s[j] 可以交换到 s[i]，则当前枚举的 i 判断成功，将 cnts[cur].front() 删除，继续枚举后面的 i
若所有 i 均判断成功，则 true

代码 (C++)

class Solution {
public:
    bool isTransformable(string s, string t) {
        int n = s.size();
        vector<list<int>> cnts(10);
        for(int i = 0; i < n; ++i)
            cnts[s[i] - '0'].push_back(i);
        for(int i = 0; i < n; ++i)
        {
            int cur = t[i] - '0';
            if(cnts[cur].empty())
                return false;
            int j = cnts[cur].front();
            for(int k = 0; k < cur; ++k)
                if(!cnts[k].empty() && cnts[k].front() < j)
                    return false;
            cnts[cur].erase(cnts[cur].begin());
        }
        return true;
    }
};

---