Solved! Leetcode 320. Generalized Abbreviation

source: https://leetcode.com/problems/generalized-abbreviation/description/

Generalized Abbreviation

A word’s generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent 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")
"5" ("abcde" turned into "5")
"abcde" (no substrings replaced)
However, these abbreviations are invalid:
"23" ("ab" turned into "2" and "cde" turned into "3") is invalid as the substrings chosen are adjacent.
"22de" ("ab" turned into "2" and "bc" turned into "2") is invalid as the substring chosen overlap.

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.

class Solution {
    public List<String> generateAbbreviations(String word) {
        Map<String, Set<String>> memo = new HashMap<>();
        List<String> res = new ArrayList<>();
        Set<String> set = dfs(word.toCharArray(), 0, &quot;&quot;, 0, memo);
        res.addAll(set);
        return res;
    }

    private Set<String> dfs(char[] arr, 
        int index,
        String curr, 
        int count, 
        Map<String, Set<String>> memo){

        if(index >= arr.length){
            if(count !=0){
                curr = curr+count;
            }
            return Set.of(curr);
        }
        String key = index+&quot;:&quot;+count+&quot;:&quot;+curr;
        if(memo.containsKey(key)){
            return memo.get(key);
        }

        //if count is not zero
        HashSet<String> set = new HashSet<>();
        if(count != 0){
            //either keep continue counting the characters
            Set<String> a = dfs(arr, index+1, curr, count+1, memo);
            set.addAll(a);
            //add the count and character to the string and reset count to zero
            Set<String> b = dfs(arr, index+1, curr+count+arr[index], 0, memo);
            set.addAll(b);
        } else {
            //if the count is zero
            //either start counting
            Set<String> a = dfs(arr, index+1, curr, count+1, memo);
            set.addAll(a);
            //or add a character to the string
            Set<String> b = dfs(arr, index+1, curr+arr[index], 0, memo);
            set.addAll(b);
        }
        memo.put(key, set);
        return set;
    }
}

class Solution {

public List<String> generateAbbreviations(String word) {

Map<String, Set<String>> memo = new HashMap<>();

List<String> res = new ArrayList<>();

Set<String> set = dfs(word.toCharArray(), 0, "", 0, memo);

res.addAll(set);

return res;

}

private Set<String> dfs(char[] arr,

int index,

String curr,

int count,

Map<String, Set<String>> memo){

if(index >= arr.length){

if(count !=0){

curr = curr+count;

}

return Set.of(curr);

}

String key = index+":"+count+":"+curr;

if(memo.containsKey(key)){

return memo.get(key);

}

//if count is not zero

HashSet<String> set = new HashSet<>();

if(count != 0){

//either keep continue counting the characters

Set<String> a = dfs(arr, index+1, curr, count+1, memo);

set.addAll(a);

//add the count and character to the string and reset count to zero

Set<String> b = dfs(arr, index+1, curr+count+arr[index], 0, memo);

set.addAll(b);

} else {

//if the count is zero

//either start counting

Set<String> a = dfs(arr, index+1, curr, count+1, memo);

set.addAll(a);

//or add a character to the string

Set<String> b = dfs(arr, index+1, curr+arr[index], 0, memo);

set.addAll(b);

}

memo.put(key, set);

return set;

}

Rate this post

Coddicted

Solved! Leetcode 320. Generalized Abbreviation

Generalized Abbreviation

Leave a Reply Cancel Reply