Skip to content

Latest commit

 

History

History
124 lines (111 loc) · 3.46 KB

1585. Check If String Is Transformable With Substring Sort Operations.md

File metadata and controls

124 lines (111 loc) · 3.46 KB
Raw

1585. Check If String Is Transformable With Substring Sort Operations

the last one in Weekly Contest 206.

Difficulty : Hard

Related Topics : String、Greedy

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'.

Solution

  • mine
    • Java
      • Runtime: 19 ms, faster than 89.57%, Memory Usage: 47.9 MB, less than 53.34% of Java online submissions 
        // O(N)time
// O(N)space
public boolean isTransformable(String s, String t) {
    int n = s.length();
    char[] arrS = s.toCharArray();
    char[] arrT = t.toCharArray();
    LinkedList<Integer>[] record = new LinkedList[10];
    for (int i = 0; i < 10; i++) {
        record[i] = new LinkedList<>();
    }
    for (int i = 0; i < n; i++) {
        record[arrS[i] - '0'].add(i);
    }
    for (int i = n - 1; i >= 0; i--) {
        int v = arrT[i] - '0';
        if (record[v].size() == 0) return false;
        int index = record[v].removeLast();
        for (int j = v + 1; j < 10; j++) {
            if (record[j].size() > 0 && record[j].getLast() > index) {
                return false;
            }
        }
    }
    return true;
}
  • the most votes
  • Runtime: 45 ms, faster than 45.30%, Memory Usage: 58.3 MB, less than 17.96% of Java online submissions 
    // O(N)time
// O(N)space
public boolean isTransformable(String s, String t) {
    ArrayList<Integer> idx[] = new ArrayList[10];
    int pos[] = new int[10];
    for (int i = 0; i <= 9; ++i)
        idx[i] = new ArrayList<Integer>();
    for (int i = 0; i < s.length(); ++i)
        idx[s.charAt(i) - '0'].add(i);
    for (int i = 0; i < t.length(); ++i) {
        int d = t.charAt(i) - '0';
        if (pos[d] >= idx[d].size())
            return false;
        for (int j = 0; j < d; ++j)
            if (pos[j] < idx[j].size() && idx[j].get(pos[j]) < idx[d].get(pos[d]))
                return false;
        ++pos[d];
    }
    return true;
}