广义缩写算法

Question

我对递归堆栈的工作原理有疑问。

我现在卡的问题是leetcode的Generalized Abbreviation

问题表明

可以通过取任意数量的非重叠子串并将它们替换为各自的长度来构造单词的广义缩写。例如，“abcde”可以缩写为“a3e”（“bcd”变成“3”）、“1bcd1”（“a”和“e”都变成“1”）、“23”（“ab” "变成了"2"，"cde"变成了"3")。

给定一个字符串词，return 一个词的所有可能通用缩写的列表。 Return 答案顺序不限。

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

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

这是我正在努力处理的代码

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static List<String> generateAbbreviations(String word){
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), word, 0, 0);
        return ans;
    }
 
    // i is the current position
    // k is the count of consecutive abbreviated characters
    private static void backtrack(List<String> ans, StringBuilder builder, String word, int i, int k){
        int len = builder.length(); // keep the length of builder 
        if(i == word.length()){
            if (k != 0) builder.append(k); // append the last k if non zero
            ans.add(builder.toString());
        } else {
            // the branch that word.charAt(i) is abbreviated
            backtrack(ans, builder, word, i + 1, k + 1);
 
            // the branch that word.charAt(i) is kept
            if (k != 0) builder.append(k);
            builder.append(word.charAt(i));
            backtrack(ans, builder, word, i + 1, 0);
        }
 
       builder.setLength(len); // reset builder to the original state
       System.out.println("Length of Stringbuilder : " + builder.length() + ",  Current element : " + builder.toString() + " , len : " + len);
    }
    public static void main(String[] args) {
    List<String> result = Ideone.generateAbbreviations("ab");
    System.out.println("Generalized abbreviation are: " + result);
  }
}

标准输出

Length of Stringbuilder : 1,  Current element : 2, len : 0
Length of Stringbuilder : 2,  Current element : 1b, len : 2
Length of Stringbuilder : 2,  Current element : 1b, len : 0
Length of Stringbuilder : 2,  Current element : a1, len : 1
Length of Stringbuilder : 2,  Current element : ab, len : 2
Length of Stringbuilder : 2,  Current element : ab, len : 1
Length of Stringbuilder : 1,  Current element : a, len : 0

输出

["2","1b","a1","ab"]

从标准输出第 2 行到第 3 行， 'len'如何从什么递归栈变成0？

Answer 1

leetcode 上的标准输出：

Length of Stringbuilder : 0,  Current element :  , len : 0
Length of Stringbuilder : 2,  Current element : 1b , len : 2
Length of Stringbuilder : 0,  Current element :  , len : 0
Length of Stringbuilder : 1,  Current element : a , len : 1
Length of Stringbuilder : 2,  Current element : ab , len : 2
Length of Stringbuilder : 1,  Current element : a , len : 1
Length of Stringbuilder : 0,  Current element :  , len : 0

函数调用将像这样（我将使用 (i, k, lenOfBuilder) 表示它们）。 lenOfBuilder 是在每个函数调用的第一行计算的长度。

对于输入词=“ab”

第一次调用 (0, 0, 0) -> 从主方法调用。

第二次调用 (1, 1, 0) -> 从第一次调用的其他条件调用的第一次回溯 ()。

第 3 次调用 (2, 2, 0) -> 第 1 次 backtrack() 从第二次调用的 else 条件调用。

Now base condition hits as (i == 2 and k != 0). So "2" added to the answer.
Return back to 2nd call.

第 4 次调用 (2, 0, 2) -> 第 2 次 backtrack() 从第二次调用的 else 条件调用。在此调用之前，我们已将“k”和 charAt(i) 添加到构建器，即“1b”

Now base condition hits as (i == 2). But K is 0. So "1b" added to the answer.
Return back to 2nd call.

Else条件第二次调用结束

现在将从函数的第二次调用开始执行以下语句。

builder.setLength(len); // As the length of builder in 2nd call was 0. So this sets the length of builder to zero -> "0".
Sysout statement will print this updated length i.e 0

这就是您的代码将构建器的长度更新为 0 的方式。在第二次调用的第一行，您已经计算出原始长度为 0。在第二次调用的其他条件结束后称呼。您将长度更新为 0 并打印 0。

广义缩写算法

Algorithms for generalized abbreviations

java

algorithm

recursion

structure

data-structures