Google – All Possible Strings

Google – All Possible Strings
Given a string that contains '', '' could be either j or k. Find out all possible strings.
[Solution]
简单题，典型backtracking咯.
但是写code的时候还是出了点小bug。backtracking的中间结果一定要想清楚再开始码代码。
Bug出在第21行。当character不是的时候，一开始写的代码在递归回来之后并没有回溯。举个例子ab就会发现，当进行到ajb的时候，递归回到处理b的那一层，如果不把b删掉，继续return到处理j的那一层，这里本意是把j删了换k，但是结果只删了b，再加上k就变成了ajk。

  public List<String> allStrings(String s) {

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

    if (s == null || s.isEmpty()) {

      return result;

    }

 

    backtracking(s, 0, result, new StringBuilder());

    return result;

  }

 

  private void backtracking(String s, int pos, List<String> result, StringBuilder sb) {

    if (pos == s.length()) {

      result.add(sb.toString());

      return;

    }

 

    if (s.charAt(pos) != '*') {

      sb.append(s.charAt(pos));

      backtracking(s, pos + 1, result, sb);

      sb.deleteCharAt(sb.length() - 1);// 一定要backtrack。

    }

    else {

      sb.append("j");

      backtracking(s, pos + 1, result, sb);

      sb.deleteCharAt(sb.length() - 1);

 

      sb.append("k");

      backtracking(s, pos + 1, result, sb);

      sb.deleteCharAt(sb.length() - 1);

    }

  }

Read full article from Google – All Possible Strings