[leetcode] 320. Generalized Abbreviation解題レポート

タイトルリンク:https://leetcode.com/problems/generalized-abbreviation/
Write a function to generate the generalized abbreviations of a word.
Example:
Given word =  "word" , return the following list (order does not matter):

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

考え方:DFS+遡及.毎回デジタル化数ビットを列挙する場合、特殊な処理が必要なのはデジタルでない場合であり、この場合は0を付けず、残りの場合はデジタルを加える.その後、インデックスを維持することは、以前の文字が処理されたことを表し、後の文字だけを処理する必要がある.それから長い間探していたバグがありました.文字列が11ビットを超えるとエラーになり、数字だけが1ビットずれていることに気づきました.
コードは次のとおりです.

class Solution {
public:
    void DFS(string word, int index)
    {
        if(index >= word.size()) 
        {
            result.push_back(word);
            return;
        }
        DFS(word, index+1);
        for(int i = index; i< word.size(); i++)
        {
            int num = word.size()-i;
            string tem = word.substr(0, index) + to_string(num) + word.substr(index+num);
            DFS(tem, index + to_string(num).size()+1);
        }
    }
    vector<string> generateAbbreviations(string word) {
        DFS(word, 0);
        return result;
    }
private:
    vector<string> result;
};