[JAVA][ZOJ 1004][Anagrams by Stack]

时间：2014-11-26 11:24:58 阅读：453 评论：0 收藏：0 [点我收藏+]

[java] view plain copy print ?

import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
static String start;// record the first str
static String end;// record the rearranged str
public static void dfs(char[] stack, char[] sequence, int posInStart, int posInEnd, int posInStack) {
if (posInStart + posInEnd == start.length() * 2) {// if all the letter has been rearranged
for (int i = 0; i < sequence.length; i++) {
System.out.print(sequence[i] + " ");// output the sequence
}
System.out.println();
}
if (posInStart < start.length()) {
sequence[posInStart + posInEnd] = ‘i‘;
stack[++posInStack] = start.charAt(posInStart);// push in
dfs(stack, sequence, posInStart + 1, posInEnd, posInStack);
posInStack--;// pop out
}
if (posInStack >= 0 && posInEnd < end.length() && stack[posInStack] == end.charAt(posInEnd)) {// pop out
sequence[posInStart + posInEnd] = ‘o‘;
posInStack--;// pop out
dfs(stack, sequence, posInStart, posInEnd + 1, posInStack);
stack[++posInStack] = end.charAt(posInEnd);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
while (sc.hasNext()) {
start = sc.next();
end = sc.next();
char[] stack = new char[start.length() * 2];// use array as the stack
char[] sequence = new char[start.length() * 2];// record the operation seq, it will have (start.length() * 2) times operations
System.out.println("[");
dfs(stack, sequence, 0, 0, -1);
System.out.println("]");
}
}
}

最近写的几道题都用到了dfs，用数组代替栈的使用，控制好stack数字下标就没什么大问题，难得一次AC

原文：http://blog.csdn.net/szhielelp/article/details/41511149

踩

(0)

评论一句话评论（0）

分享档案

更多>