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.

Rust Solution

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);
}

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