C++/C/Java: Anagrams - 从原始字符串到目标；

2022-01-22 00:00:00 algorithm c stack c++ java

我正在尝试解决这个问题:http://uva.onlinejudge.org/external/7/732.html.对于给定的示例，它们为我们提供了原始单词，例如 TRIT 和目标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.

目标:我们必须输出所有有效的'i'和'o'序列(分别是push和pop's)，它们从源字符串产生目标字符串.

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)如果找到i"命令并且输入字符串中没有任何内容，则跳过该情况.

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.

有人可以和我分享一些代码和/或想法吗?

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

P.S.:当然，欢迎任何可能减少执行时间的建议.

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

推荐答案

这个第一次迭代解决方案很有启发性.它不是最有效的，因为它到处使用 String，但它是一个很好的起点.

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");
    }
}

相关文章