1585. Check If String Is Transformable With Substring Sort Operations
Description
Given two strings s and t, transform string s into string t using the following operation any number of times:
- Choose a non-empty substring in
sand sort it in place so the characters are in ascending order.<ul> <li>For example, applying the operation on the underlined substring in <code>"1<u>4234</u>"</code> results in <code>"1<u>2344</u>"</code>.</li> </ul> </li>
Return true if it is possible to transform s into t. Otherwise, return false.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "84532", t = "34852" Output: true Explanation: You can transform s into t using the following sort operations: "84532" (from index 2 to 3) -> "84352" "84352" (from index 0 to 2) -> "34852"
Example 2:
Input: s = "34521", t = "23415" Output: true Explanation: You can transform s into t using the following sort operations: "34521" -> "23451" "23451" -> "23415"
Example 3:
Input: s = "12345", t = "12435" Output: false
Constraints:
s.length == t.length1 <= s.length <= 105sandtconsist of only digits.
Solutions
Solution 1: Bubble Sort
The problem is essentially equivalent to determining whether any substring of length 2 in string $s$ can be swapped using bubble sort to obtain $t$.
Therefore, we use an array $pos$ of length 10 to record the indices of each digit in string $s$, where $pos[i]$ represents the list of indices where digit $i$ appears, sorted in ascending order.
Next, we iterate through string $t$. For each character $t[i]$ in $t$, we convert it to the digit $x$. We check if $pos[x]$ is empty. If it is, it means that the digit in $t$ does not exist in $s$, so we return false. Otherwise, to swap the character at the first index of $pos[x]$ to index $i$, all indices of digits less than $x$ must be greater than or equal to the first index of $pos[x]. If this condition is not met, we return false. Otherwise, we pop the first index from $pos[x]$ and continue iterating through string $t$.
After the iteration, we return true.
The time complexity is $O(n \times C)$, and the space complexity is $O(n)$. Here, $n$ is the length of string $s$, and $C$ is the size of the digit set, which is 10 in this problem.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}