[LeetCode]#942. DI String Match

Environment: Python 3.7

Key technique: append function

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:

Analysis:

  1. Set low=0 and high is 4 based on S.
  2. If S[i] is “I”, add low to ans list and low add 1.
  3. If S[i] is “D”, add high to ans list and high decrease 1.
  4. The last list you can add low and high are OK.

Solution:

Submissions:

Reference:

https://leetcode.com/problems/di-string-match/solution/

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store