903. Valid Permutations for DI Sequence

We are given S, a length n string of characters from the set {'D', 'I'}. (These letters stand for "decreasing" and "increasing".)

valid permutation is a permutation P[0], P[1], ..., P[n] of integers {0, 1, ..., n}, such that for all i:

  • If S[i] == 'D', then P[i] > P[i+1], and;
  • If S[i] == 'I', then P[i] < P[i+1].

How many valid permutations are there?  Since the answer may be large, return your answer modulo 10^9 + 7.

 

Example 1:

Input: "DID"
Output: 5
Explanation: 
The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

 

Note:

  1. 1 <= S.length <= 200
  2. S consists only of characters from the set {'D', 'I'}.

 

Rust Solution

struct Solution;

const MOD: i64 = 1_000_000_007;

impl Solution {
    fn num_perms_di_sequence(s: String) -> i32 {
        let n = s.len();
        let s: Vec<char> = s.chars().collect();
        let mut memo = vec![vec![-1; n + 1]; n + 1];
        for j in 0..=n {
            memo[n][j] = 1;
        }
        Self::dp(0, 0, &mut memo, &s, n) as i32
    }

    fn dp(i: usize, j: usize, memo: &mut Vec<Vec<i64>>, s: &[char], n: usize) -> i64 {
        if memo[i][j] != -1 {
            memo[i][j]
        } else {
            let mut res = 0;
            if s[i] == 'I' {
                for k in j + 1..=i + 1 {
                    res += Self::dp(i + 1, k, memo, s, n);
                    res %= MOD;
                }
            }
            if s[i] == 'D' {
                for k in 0..=j {
                    res += Self::dp(i + 1, k, memo, s, n);
                    res %= MOD;
                }
            }
            memo[i][j] = res;
            res
        }
    }
}

#[test]
fn test() {
    let s = "DID".to_string();
    let res = 5;
    assert_eq!(Solution::num_perms_di_sequence(s), res);
    let s = "D".to_string();
    let res = 1;
    assert_eq!(Solution::num_perms_di_sequence(s), res);
}

Having problems with this solution? Click here to submit an issue on github.