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

Question

我正在做一个来自http://oncecoder.blogspot.com.au/2015/08/abba-srm-663-div-2-500.html的问题

有一天，杰米注意到许多英语单词只使用字母A和B。这类单词的例子包括"AB“(腹部的缩写)、"BAA”(羊发出的噪音)、"AA“(熔岩的一种类型)和"ABBA”(瑞典流行流行音乐)。 受到这一观察的启发，杰米创造了一个简单的游戏。您将得到两个字符串:初始字符串和目标字符串。游戏的目标是找到一系列有效的移动，将初始变为目标。有两种类型的有效移动： 将字母A添加到字符串的末尾。 反转字符串，然后将字母B添加到字符串的末尾。返回“可能”(引号明确)，如果有一系列有效的移动，将改变初始为目标。否则，返回“不可能”。

我的问题：

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，则只能通过规则2从zyx获得。所以在伪码中，

    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"

当然，逆转并不一定是明确的。

Answer 2

这是一个线性时间为O(n)的解。其思想是从目标字符串开始，然后尝试还原操作，直到到达与初始字符串长度相同的字符串为止。然后比较这两个字符串。以下是解决办法：

   private static final char A = 'A';
   private static final String POSSIBLE = "Possible";
   private static final String IMPOSSIBLE = "Impossible";

   public String canObtain(String initial, String target) {
      if (initial == null ||
            initial.trim().length() < 1 ||
            initial.trim().length() > 999) {
         return IMPOSSIBLE;
      }

      if (target == null ||
            target.trim().length() < 2 ||
            target.trim().length() > 1000) {
         return IMPOSSIBLE;
      }

      return isPossible(initial, target) ? POSSIBLE : IMPOSSIBLE;
   }

   private boolean isPossible(String initial, String target) {
      final StringBuilder sb = new StringBuilder(target);
      while (initial.length() != sb.length()) {
         char targetLastChar = sb.charAt(sb.length() - 1);
         if (targetLastChar == A) {
            unApplyA(sb);
         } else {
            unApplyRevB(sb);
         }
      }

      return initial.equals(sb.toString());
   }

   private void unApplyA(StringBuilder sb) {
      sb.deleteCharAt(sb.length() - 1);
   }

   private void unApplyRevB(StringBuilder sb) {
      sb.deleteCharAt(sb.length() - 1);
      sb.reverse();
   }

Answer 3

聚会有点晚了，但这是Python中的一个简洁的解决方案，在线性时间内运行：

class ABBA:
    def canObtain(self, initial, target):
        if initial == target:
            return 'Possible'
        if len(initial) == len(target):
            return 'Impossible'
        if target[-1] == 'A':
            return self.canObtain(initial, target[:-1])
        if target[-1] == 'B':
            return self.canObtain(initial, target[:-1][::-1])