C ++ / C / Java的：字谜 - 从原来的字符串到目标; [英] C++/C/Java: Anagrams - from original string to target;

问题描述

我试图来解决这个问题： http://uva.onlinejudge.org /external/7/732.html 。 对于给定的例子中，他们给我们原来的字，例如三叔和目标anagramed字符串， TIRT

I'm trying to solve this problem : http://uva.onlinejudge.org/external/7/732.html. For the given example, they give us the original word, for example TRIT and the target "anagramed" string, TIRT.

目标：我们要输出的'我'（，push和pop的分别）所有有效序列和'O'的产生从源字符串目标字符串

Objective: We have to output all the valid sequences of 'i' and 'o' (push and pop's, respectively) which produce the target string from the source string.

所以，我在想计算的i和o的所有排列，但切割这个情况：

So, I was thinking of calculate all permutations of "i" and "o" , but cutting this cases:

1）如果当前排列始于一个O，停止检查，因为在接下来的排列都将开始使用此弹出命令，并从一个空堆栈弹出的东西是一个无效的命令。

1) if current permutation begins with an 'o', stop checking, since all the of the next permutations will begin with this pop command and popping something from an empty stack is an invalid command.

2）如果一个O命令，被发现在该检查的中间并没有什么堆栈中，跳过情况。

2) if an 'o' command is found in the middle of the checking and there is nothing in the stack, skip that case.

3）如果一个'我'命令发现并没有什么输入字符串，跳过情况。

3) if an 'i' command is found and there is nothing in the input string, skip that case.

4）如果一个O命令被发现，目前预期的性格不只是冒出来的字符，然后跳到这种情况下，因为这将永远达不到目标字符串。

4) if an 'o' command is found and currently expected character is not the character just popped out, then skip that case, since this will never reach to the target string.

5）不要搜索，如果输入和目标字符串有不同的长度。

5) don't search if the input and target strings have different lengths.

但我认为这可能让我反正TLE ...

but I think it might get me TLE anyway...

我知道这个原理：排列也许并回溯一路。 我只是实现它太多的困难。

I know the theory: permutations perhaps and backtracking all the way. I just have too many difficulties implementing it.

可能有人请与我分享一些code和或想法，请？

could anyone please share with me some code and or ideas please?

PS：任何建议，可能会降低一些执行时间将是当然欢迎，

P.S.: Any suggestion that may decrease some execution time will be welcome , of course.

推荐答案

这第一次迭代的解决方案是有益的。这不是最有效的，因为它使用字符串所有的地方，但它是一个良好的开端。

This first iteration solution is instructive. It's not the most efficient since it uses String all over the place, but it's a good place to start.

import java.util.*;

public class StackAnagram {

    static void anagram(String s1, String s2, String stack, String instr) {
        if (s2.isEmpty()) {
            if (s1.isEmpty() && stack.isEmpty()) {
                System.out.println(instr.trim());
            }
            return;
        }
        if (!s1.isEmpty()) {
            anagram(s1.substring(1), s2, s1.charAt(0) + stack, instr + "i ");
        }
        if (!stack.isEmpty() && stack.charAt(0) == s2.charAt(0)) {
            anagram(s1, s2.substring(1), stack.substring(1), instr + "o ");
        }
    }

    static void anagram(String s1, String s2) {
        System.out.println("[");
        anagram(s1, s2, "", "");
        System.out.println("]");
    }

    public static void main(String args[]) {
        anagram("madam", "adamm");
        anagram("bahama", "bahama");
        anagram("long", "short");
        anagram("eric", "rice");
        anagram("ericc", "rice");
    }
}

这篇关于C ++ / C / Java的：字谜 - 从原来的字符串到目标;的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！