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
s
and 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.length
1 <= s.length <= 105
s
andt
only contain digits from'0'
to'9'
.
A:
稍微试了几个, 找到了原理, 就是 每次找t中的下一个char , 然后在s中 查找, 在找到该char之前的所有的char,不能比他小,否则就 sort不过来。
sol 1: 每次找到一个, 用类似bubble sort的方式 float up
class Solution { public: bool isTransformable(string s, string t) { int n = s.length(); //idea: switch to make the first char, by switch one by one, to keep order for(int start =0; start < n; start++){ int targetIndex = start; while(targetIndex < n && s[targetIndex] != t[start]){ targetIndex++; } if(targetIndex >= n){ return false; } // bubble sort to float up the target char for(int i =targetIndex; i> start;i--){ if(s[i-1] < t[start]){ // make sure all can be floated up return false; } s[i] = s[i-1]; } } return true; } };
逻辑是正确的。 然而LTE了。 上面太多的move操作,而且重复了。
现在,去掉重复move, 改用一个数组来flag一个char 是否visited了
class Solution { public: bool isTransformable(string s, string t) { int n = s.length(); vector<bool> visited(n, false); //idea: switch to make the first char, by switch one by one, to keep order int startS = 0; for(int it =0; it < n; it++){ char targetChar = t[it]; int is=startS; while(is< n && (visited[is] || s[is] > targetChar ) ){ is++; } if(is >= n || s[is] != targetChar){ return false; } visited[is] = true; while(startS < n && visited[startS]){// amortized time complexity is O(1) startS++; } } return true; } };
我XXXXXXX ,竟然还 LTE
看了下结果, 是0--9 可能一个位置,有太多重复的了。看这个例子。
所以,优化只能是第一个while
那么,我们用一个数组来记录每个char的位置, 这样就不用挨个查了。(最多查9个,所以还是O(1)的复杂度)
class Solution { public: bool isTransformable(string s, string t) { int n = s.length(); vector<vector<int>> Pos(10, vector<int>()); for (int i = n - 1; i >= 0; i--) { Pos[s[i] - '0'].push_back(i); } for (int i = 0; i < n; i++) { int val = t[i] - '0'; // check that no values smaller than val, is ahead of it. if (Pos[val].empty()) { return false; } int valPos = Pos[val].back(); for (int v = 0; v < val; v++) { if (!Pos[v].empty() && Pos[v].back() < valPos) { return false; } } Pos[val].pop_back(); } return true; } }
No comments:
Post a Comment