Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/942.html

Given a string `S` that only contains "I" (increase) or "D" (decrease), let `N = S.length`.
Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]
If S[i] == "D", then A[i] > A[i+1]
Example 1:

Input: "IDID"
Output: [0,4,1,3,2]
Example 2:

Input: "III"
Output: [0,1,2,3]
Example 3:

Input: "DDI"
Output: [3,2,0,1]
Note:

1 <= S.length <= 10000
S only contains characters "I" or "D".

Algorithm

This question gives a string consisting of only the two letters’D’ and’I’, which represents a pattern, where’D’ means that needs to be decreased, that is, the current number is greater than the next number, the same is true,’i’ Indicates the need to increase, that is, the current number is less than the next number, so that any array that meets this requirement is returned.

Another requirement is that the array must be a full arrangement of all numbers between [0, n], where n Is the length of the given pattern string. This indicates that the returned array cannot have duplicate numbers.

Here, it will rise and then drop. It is easy to produce duplicate numbers. Is it necessary to keep checking whether there are duplicate numbers? No, this is too time consuming. You must make sure the generated methods ensuring that there will never be repeated numbers. For rising, you can start accumulating from 0, and for falling, you can start to decrease from n. This ensures that the two will never meet before the end. When the two are the same when the last number is reached, add this Just add the same number, because the number of returned arrays will always be one larger than the length of the given string, see the code as follows:

Code

C++

class Solution {
public:
    vector<int> diStringMatch(string S) {
		vector<int> res;
		int n = S.size(), mn = 0, mx = n;
		for (char c : S) {
			if (c == 'I') res.push_back(mn++);
			else res.push_back(mx--);
		}
        res.push_back(mx);
		return res;
    }
};

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public int[] diStringMatch(String S) {
          int strLength = S.length();
          int length = strLength + 1;
          int[] array = new int[length];
          int min = 0, max = 0;
          for (int i = 1; i < length; i++) {
              char c = S.charAt(i - 1);
              int newNum = c == 'I' ? max + 1 : min - 1;
              array[i] = newNum;
              min = Math.min(min, newNum);
              max = Math.max(max, newNum);
          }
          if (min != 0) {
              for (int i = 0; i < length; i++)
                  array[i] -= min;
          }
          return array;
      }
  }
  
  ############
  
  class Solution {
      public int[] diStringMatch(String s) {
          int n = s.length();
          int low = 0, high = n;
          int[] ans = new int[n + 1];
          for (int i = 0; i < n; i++) {
              if (s.charAt(i) == 'I') {
                  ans[i] = low++;
              } else {
                  ans[i] = high--;
              }
          }
          ans[n] = low;
          return ans;
      }
  }
  
  

• // OJ: https://leetcode.com/problems/di-string-match/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      vector<int> diStringMatch(string S) {
          vector<int> ans(S.size() + 1, 0);
          int lo = 0, hi = S.size();
          for (int i = 0; i < S.size(); ++i) {
              ans[i] = S[i] == 'I' ? lo++ : hi--;
          }
          ans[S.size()] = lo;
          return ans;
      }
  };
  

• class Solution:
      def diStringMatch(self, s: str) -> List[int]:
          n = len(s)
          low, high = 0, n
          ans = []
          for i in range(n):
              if s[i] == 'I':
                  ans.append(low)
                  low += 1
              else:
                  ans.append(high)
                  high -= 1
          ans.append(low)
          return ans
  
  ############
  
  class Solution:
      def diStringMatch(self, S):
          """
          :type S: str
          :rtype: List[int]
          """
          N = len(S)
          ni, nd = 0, N
          res = []
          for s in S:
              if s == "I":
                  res.append(ni)
                  ni += 1
              else:
                  res.append(nd)
                  nd -= 1
          res.append(ni)
          return res 
  

• func diStringMatch(s string) []int {
  	n := len(s)
  	low, high := 0, n
  	var ans []int
  	for i := 0; i < n; i++ {
  		if s[i] == 'I' {
  			ans = append(ans, low)
  			low++
  		} else {
  			ans = append(ans, high)
  			high--
  		}
  	}
  	ans = append(ans, low)
  	return ans
  }
  
  

• function diStringMatch(s: string): number[] {
      const n = s.length;
      const res = new Array(n + 1);
      let low = 0;
      let high = n;
      for (let i = 0; i < n; i++) {
          if (s[i] === 'I') {
              res[i] = low++;
          } else {
              res[i] = high--;
          }
      }
      res[n] = low;
      return res;
  }
  
  

• impl Solution {
      pub fn di_string_match(s: String) -> Vec<i32> {
          let s = s.as_bytes();
          let n = s.len();
          let mut res = Vec::with_capacity(n + 1);
          let (mut low, mut high) = (-1, (n + 1) as i32);
          for i in 0..n {
              res.push(if s[i] == b'I' {
                  low += 1;
                  low
              } else {
                  high -= 1;
                  high
              });
          }
          res.push(low + 1);
          res
      }
  }
  
  

All Problems

All Solutions