38. Count and Say Medium

1/**
2 * [38] Count and Say
3 *
4 * The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
5 *
6 * countAndSay(1) = "1"
7 * countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.
8 *
9 * To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
10 * For example, the saying and conversion for digit string "3322251":
11 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/23/countandsay.jpg" style="width: 581px; height: 172px;" />
12 * Given a positive integer n, return the n^th term of the count-and-say sequence.
13 *  
14 * Example 1:
15 *
16 * Input: n = 1
17 * Output: "1"
18 * Explanation: This is the base case.
19 *
20 * Example 2:
21 *
22 * Input: n = 4
23 * Output: "1211"
24 * Explanation:
25 * countAndSay(1) = "1"
26 * countAndSay(2) = say "1" = one 1 = "11"
27 * countAndSay(3) = say "11" = two 1's = "21"
28 * countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
29 *
30 *  
31 * Constraints:
32 *
33 * 1 <= n <= 30
34 *
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/count-and-say/
39// discuss: https://leetcode.com/problems/count-and-say/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn count_and_say(n: i32) -> String {
45        Self::cns(n, "1".to_string())
46    }
47
48    fn cns(n: i32, p: String) -> String {
49        if n <= 1 {
50            return p;
51        }
52        let mut result = String::new();
53
54        let (mut c, mut s) = (&p[0..1], 0);
55        for i in 1..p.len() {
56            if &p[i..i + 1] != c {
57                result.push_str(&(i - s).to_string());
58                result.push_str(c);
59                c = &p[i..i + 1];
60                s = i;
61            }
62        }
63        result.push_str(&(p.len() - s).to_string());
64        result.push_str(c);
65        Self::cns(n - 1, result)
66    }
67}
68
69// submission codes end
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_38() {
77        assert_eq!(Solution::count_and_say(4), "1211".to_owned());
78    }
79}
80