Given two strings s and t, you want to 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.
For example, applying the operation on the underlined substring in "14234" results in "12344".
Return true if it is possible to transform string s into string 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
Example 4:
Input: s = "1", t = "2" Output: false
Constraints:
s.length == t.length1 <= s.length <= 105sandtonly contain digits from'0'to'9'.
Solution: Queue
We can move a smaller digit from right to left by sorting two adjacent digits.
e.g. 18572 -> 18527 -> 18257 -> 12857, but we can not move a larger to the left of a smaller one.
Thus, for each digit in the target string, we find the first occurrence of it in s, and try to move it to the front by checking if there is any smaller one in front of it.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: bool isTransformable(string s, string t) { vector<deque<int>> idx(10); for (int i = 0; i < s.length(); ++i) idx[s[i] - '0'].push_back(i); for (char c : t) { const int d = c - '0'; if (idx[d].empty()) return false; for (int i = 0; i < d; ++i) if (!idx[i].empty() && idx[i].front() < idx[d].front()) return false; idx[d].pop_front(); } return true; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution: def isTransformable(self, s: str, t: str) -> bool: idx = defaultdict(deque) for i, c in enumerate(s): idx[int(c)].append(i) for c in t: d = int(c) if not idx[d]: return False for i in range(d): if idx[i] and idx[i][0] < idx[d][0]: return False idx[d].popleft() return True |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment