320. Generalized Abbreviation

A word's generalized abbreviation can be constructed by taking any number of non-overlapping substrings and replacing them with their respective lengths. For example, "abcde" can be abbreviated into "a3e" ("bcd" turned into "3"), "1bcd1" ("a" and "e" both turned into "1"), and "23" ("ab" turned into "2" and "cde" turned into "3").

Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.

 

Example 1:

Input: word = "word"
Output: ["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]

Example 2:

Input: word = "a"
Output: ["1","a"]

 

Constraints:

  • 1 <= word.length <= 15
  • word consists of only lowercase English letters.

320. Generalized Abbreviation
struct Solution;

impl Solution {
    fn generate_abbreviations(word: String) -> Vec<String> {
        let n = word.len();
        let word: Vec<char> = word.chars().collect();
        let mut cur: String = "".to_string();
        let mut res = vec![];
        Self::dfs(0, 0, &mut cur, &mut res, &word, n);
        res
    }

    fn dfs(
        start: usize,
        count: usize,
        cur: &mut String,
        all: &mut Vec<String>,
        word: &[char],
        n: usize,
    ) {
        let len = cur.len();
        if start == n {
            if count > 0 {
                *cur += &count.to_string();
            }
            all.push((*cur).to_string());
        } else {
            Self::dfs(start + 1, count + 1, cur, all, word, n);
            if count > 0 {
                *cur += &count.to_string();
            }
            cur.push(word[start]);
            Self::dfs(start + 1, 0, cur, all, word, n);
        }
        cur.truncate(len);
    }
}

#[test]
fn test() {
    let word = "word".to_string();
    let mut res = vec_string![
        "word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2",
        "2r1", "3d", "w3", "4"
    ];
    let mut ans = Solution::generate_abbreviations(word);
    res.sort();
    ans.sort();
    assert_eq!(ans, res);
}