Skip to content

Instantly share code, notes, and snippets.

@wang-nima
Created January 10, 2021 03:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save wang-nima/ffa2fe59050999ddffe1c6b1953b692c to your computer and use it in GitHub Desktop.
Save wang-nima/ffa2fe59050999ddffe1c6b1953b692c to your computer and use it in GitHub Desktop.
public static void assign(int n) {
// out put strings in this method.
StringBuilder sb = new StringBuilder();
backtracking(0, n, sb);
}
private static void backtracking(int index, int n, StringBuilder sb) {
if (index == n) {
System.out.println(sb.toString());
return;
}
// 3 cases we can append D
// 1. empty string builder
// 2. previous char is T. (index >= 1)
// 3. previous char is D but, previous 2 char is T (index >= 2) or
boolean case1 = sb.length() == 0;
boolean case2 = index >= 2 && sb.charAt(index - 1) == 'D' && sb.charAt(index - 2) == 'T';
boolean case3 = index >= 1 && sb.charAt(index - 1) == 'T';
boolean case4 = index == 1 && sb.charAt(0) == 'D';
if (case1 || case2 || case3 || case4) {
sb.append("D");
backtracking(index+1, n, sb);
sb.deleteCharAt(sb.length() - 1);
}
// 2 cases we can append T
// 1. empty string builder
// 2. previous char is D (index >= 1)
if (sb.length() == 0 || index >= 1 && sb.charAt(index - 1) == 'D') {
sb.append("T");
backtracking(index+1, n, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment