跳转至

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

来源第 206 场周赛 Q4难度困难分数2333

题目描述

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

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

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

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

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

 

示例 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

 

提示：

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

解法

方法一：冒泡排序

思考

对任意子串排序若干次，问 \(s\) 能否变成 \(t\)。子串排序等价于相邻逆序对的冒泡：较大数字不能越过左侧更小的数字。\(n\le 10^5\)，不能模拟每一次排序。

记下 \(s\) 中每个数字的下标队列。按 \(t\) 的顺序取出数字 \(x\) 的最左出现：若存在更小数字仍停在它左边，则无法把它换到当前位。否则弹出该下标继续。频次不足也失败。

题目实际上等价于判断：将字符串 \(s\) 中任意长度为 \(2\) 的子字符串采用冒泡排序交换，是否能得到 \(t\)。

因此我们用一个长度为 \(10\) 的数组 \(pos\) 记录字符串 \(s\) 中每个字符数字的下标，其中 \(pos[i]\) 表示数字 \(i\) 出现的下标列表，按从小到大排序。

接下来，我们遍历字符串 \(t\)，对于 \(t\) 中的每个字符 \(t[i]\)，我们转为数字 \(x\)，我们判断 \(pos[x]\) 是否为空，若是，说明字符串 \(s\) 中不存在 \(t\) 中的数字，直接返回 false。否则，若要将 \(pos[x]\) 的第一个位置下标的字符交换到下标 \(i\) 的位置，需要满足小于 \(x\) 的所有数字的下标均不小于 \(pos[x]\) 的第一个位置下标，若不满足，返回 false。否则，我们将 \(pos[x]\) 的第一个位置下标弹出，然后继续遍历字符串 \(t\)。

遍历结束，返回 true。

时间复杂度 \(O(n \times C)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为字符串 \(s\) 的长度，而 \(C\) 是数字集的大小，本题中 \(C=10\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def isTransformable(self, s: str, t: str) -> bool:
        pos = defaultdict(deque)
        for i, c in enumerate(s):
            pos[int(c)].append(i)
        for c in t:
            x = int(c)
            if not pos[x] or any(pos[i] and pos[i][0] < pos[x][0] for i in range(x)):
                return False
            pos[x].popleft()
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isTransformable(String s, String t) {
        Deque<Integer>[] pos = new Deque[10];
        Arrays.setAll(pos, k -> new ArrayDeque<>());
        for (int i = 0; i < s.length(); ++i) {
            pos[s.charAt(i) - '0'].offer(i);
        }
        for (int i = 0; i < t.length(); ++i) {
            int x = t.charAt(i) - '0';
            if (pos[x].isEmpty()) {
                return false;
            }
            for (int j = 0; j < x; ++j) {
                if (!pos[j].isEmpty() && pos[j].peek() < pos[x].peek()) {
                    return false;
                }
            }
            pos[x].poll();
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isTransformable(string s, string t) {
        queue<int> pos[10];
        for (int i = 0; i < s.size(); ++i) {
            pos[s[i] - '0'].push(i);
        }
        for (char& c : t) {
            int x = c - '0';
            if (pos[x].empty()) {
                return false;
            }
            for (int j = 0; j < x; ++j) {
                if (!pos[j].empty() && pos[j].front() < pos[x].front()) {
                    return false;
                }
            }
            pos[x].pop();
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func isTransformable(s string, t string) bool {
    pos := [10][]int{}
    for i, c := range s {
        pos[c-'0'] = append(pos[c-'0'], i)
    }
    for _, c := range t {
        x := int(c - '0')
        if len(pos[x]) == 0 {
            return false
        }
        for j := 0; j < x; j++ {
            if len(pos[j]) > 0 && pos[j][0] < pos[x][0] {
                return false
            }
        }
        pos[x] = pos[x][1:]
    }
    return true
}

评论