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
s
and 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.length
1 <= s.length <= 105
s
andt
consist of only digits.
Solution
Python3
class Solution:
def isTransformable(self, s: str, t: str) -> bool:
N = len(s)
index = [[] for _ in range(10)]
count = [0] * 10
for i, x in enumerate(s):
index[int(x)].append(i)
for x in t:
d = int(x)
if count[d] >= len(index[d]):
return False
# loop through 1...d
# to check if index[k][count[k]] is < index[d][count[d]],
# which means k is unable to swap with d, due to d is always larger than k
for k in range(d):
if count[k] < len(index[k]) and index[k][count[k]] < index[d][count[d]]:
return False
count[d] += 1
return True