abbreviation

1. Generalized Abbreviation

문제: https://leetcode.com/problems/generalized-abbreviation/

Account Login - LeetCode

 string이 주어질때 길이만큼 숫자로 줄이는 문제다.  예를 들면, "abcdefg"가 있을 때 a는 길이가 1이므로 "1bcdefg"로 줄일 수 있다.  다만 숫자가 연속되면 안되는 제약이 있다.

 

class Solution {
public:
    vector<string> ans;
    
    void traverse(string word, int start, string partial){
        int n = word.size();
        if(start >= n){
            ans.push_back(partial);
            return;
        }
        
        for(int i = start; i < n; i++){
            for(int j = i; j < n; j++){
                string next = partial + word.substr(start, i - start) + to_string(j - i + 1) + word.substr(j + 1, 1);
                traverse(word, j + 2, next);
            }
        }
        traverse(word, n, partial + word.substr(start, n - start));
    }
    
    vector<string> generateAbbreviations(string word) {
        traverse(word, 0, "");
        return ans;
    }
};

 start에서 생각할 수 있는 모든 케이스에 대해서 traverse를 돈다.  이중루프에서는 abbreviation이 되는 케이스만 들어가므로 abbreviation이 되지 않는 케이스를 이후에 콜한다.