1585. Check If String Is Transformable With Substring Sort Operations ------ H ~~~

 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 and t 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;
    }
}