时间戳

首页 > 解决方案 > 为什么删除 StringBuilder 语法错误中的最后一个字符？

java - 为什么删除 StringBuilder 语法错误中的最后一个字符？

问题描述

public ArrayList<String> printPaths(char[][] board){
    ArrayList<String> out = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    search(0,0,board,sb,out);
    return out;
}

public void search(int i, int j, char[][] board, StringBuilder sb, ArrayList<String> out){
    int rows = board.length;
    int cols = board[0].length;
    if(i > rows-1 || j > cols-1) return;

    sb.append(board[i][j]); // Mark
    if(i == rows-1 && j == cols-1){
        out.add(sb.toString());
        sb.deleteCharAt(sb.length()-1);
        return;
    }
    search(i+1,j,board,sb,out); // Search Down
    search(i,j+1,board,sb,out); // Search Right
    sb.deleteCharAt(sb.length()-1); // Un-Mark
}

在段落之间放置换行符 在末尾添加两个空格 ► 修复语法或拼写错误 ► 澄清含义而不更改它 ► 纠正小错误 ► 添加相关资源或链接 ► 始终尊重原作者 ► 修复语法或拼写错误 ► 澄清含义而不更改它 ► 纠正小错误 ► 添加相关资源或链接 ► 永远尊重原作者

标签： javarecursion

解决方案

这是回溯逻辑。以这种方式查看这些说明（添加评论）：

sb.append(board[i][j]); // Mark
if(i == rows-1 && j == cols-1){
    out.add(sb.toString());

   /*
   Here, you reached the bottom-right element of the matrix. 
   You can no longer go down or right, so you perform a backtracking 
   by deleting the last element read. 
   */
    sb.deleteCharAt(sb.length()-1);
    return;
}
search(i+1,j,board,sb,out); // Search Down
search(i,j+1,board,sb,out); // Search Right

/*
Here, you exhausted the elements on bottom and right 
(because you just returned from the two search() calls). Perform a backtracking by
removing the last element (which is a dead end) before returning to the calling 
recursion step:
*/
sb.deleteCharAt(sb.length()-1); // Un-Mark

推荐阅读