算法 ABBA(SRM 663, DIV 2, 500)

Question

我正在做一个来自 this blog 的问题

One day, Jamie noticed that many English words only use the letters A and B. Examples of such words include "AB" (short for abdominal), "BAA" (the noise a sheep makes), "AA" (a type of lava), and "ABBA" (a Swedish pop sensation).

Inspired by this observation, Jamie created a simple game. You are given two Strings: initial and target. The goal of the game is to find a sequence of valid moves that will change initial into target. There are two types of valid moves:

Add the letter A to the end of the string.
Reverse the string and then add the letter B to the end of the string.Return "Possible" (quotes for clarity) if there is a sequence of valid moves that will change initial into target. Otherwise, return "Impossible".

我的问题:

1. 我的解决方案遵循示例步骤:首先，反转并附加“B”，然后附加“A”。我不知道我是否需要同时使用另一个步骤顺序(首先，附加“A”，然后反转并附加“B”)。
2. 我得到“ABBA”，它应该返回“可能”，但返回“不可能”。

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(canContain("B","ABBA"));
}

public static String canContain(String Initial, String Target){ 
    
    char[] target = new char[1000];
    char[] initial1 = new char[1000];
    int flag = 0;
    boolean possible = false;
    int InitialLength = Initial.length();
    int TargetLength = Target.length();
    
    System.out.println("Initial:");
    int countInitial = -1;
    for(char x : Initial.toCharArray()){
        countInitial++;
        if(x=='A')initial1[countInitial]='A';
        if(x=='B')initial1[countInitial]='B';
        System.out.print(x+"->"+initial1[countInitial]+" ");
    }
    
    
    int countTarget = -1;
    System.out.println("\nTarget:");
    for(char y : Target.toCharArray()){
        countTarget++;
        if(y=='A')target[countTarget]='A';
        if(y=='B')target[countTarget]='B';
        System.out.print(y+"->"+target[countTarget]+" ");
    }
    System.out.print("\n");
    
    
    
    //Check Initial char[]
    System.out.print("---------------");
    System.out.print("\n");
    for(int t1 = 0; t1 <= countInitial; t1++){
        System.out.print(initial1[t1]+"-");
    }
    System.out.print("\n");
    for(int t3 = 0; t3 <= countTarget; t3++){
        System.out.print(target[t3]+"-");
    }
    
    while(countInitial != countTarget){
        if(flag == 0 && Initial != Target){
            System.out.println("\n_______A_______");
            countInitial++;
            System.out.println("countInitial = "+countInitial);
            initial1[countInitial] = 'A';
            System.out.println(initial1[countInitial]);
            for(int t1 = 0; t1 <= countInitial; t1++){
                System.out.print(initial1[t1]+"-");
            }
            flag = 1;
        }else if(flag == 1 && Initial != Target){
            System.out.println("\n_______R_+_B_______");
            int ct = 0;
            char[] temp = new char[1000];
            for(int i = countInitial; i >= 0; i--){
                System.out.println("countInitial = "+countInitial);
                temp[ct] = initial1[i];
                System.out.println("ct = "+ct);
                ct++;
            }
            initial1 = temp;
            countInitial++;
            initial1[countInitial] = 'B';
            for(int t1 = 0; t1 < countInitial; t1++){
                System.out.print(initial1[t1]+"-");
            }
            flag = 0;
        }
    }
    
    if(initial1.equals(target)){
        return "Possible";
    }else{
        return "Impossible";
    }
    
}

Answer 1

您的直接问题是您按特定顺序应用规则。但是，不禁止连续多次使用相同的规则。因此，要从初始字符串中获取目标字符串，您需要检查所有可能的规则应用程序序列。这被称为组合爆炸。

像这样的问题通常更容易逆向解决。如果目标字符串是 xyzA，它只能通过规则 1 从 xyz 获得。如果目标字符串是 xyzB，它只能通过 zyx 的规则 2 获得。所以在伪代码中，

    while length(target) > length(initial)
        remove the last letter from target
        if removed letter is "B"
            reverse target
    if target == initial
        print "Possible"
    else
        print "Impossible"

当然，逆转不必是明确的。