This question involves reasoning about strings made up of uppercase letters. You will implement two related methods that appear in the same class (not shown). The first method takes a single string parameter and returns a scrambled version of that string. The second method takes a list of strings and modifies the list by scrambling each entry in the list. Any entry that cannot be scrambled is removed from the list.

Write the method scrambleWord, which takes a given word and returns a string that contains a scrambled version of the word according to the following rules.

  • The scrambling process begins at the first letter of the word and continues from left to right.
  • If two consecutive letters consist of an “A” followed by a letter that is not an “A”, then the two letters are swapped in the resulting string.
  • Once the letters in two adjacent positions have been swapped, neither of those two positions can be involved in a future swap.

The following table shows several examples of words and their scrambled versions.

import java.util.List;
import java.util.ArrayList;

public class ScrambledStrings
{
   /********************** Part (a) *********************/

   /** Scrambles a given word.
    *  @param word the word to be scrambled
    *  @return the scrambled word (possibly equal to word)
    *  Precondition: word is either an empty string or
    *                contains only uppercase letters.
    *  Postcondition: the string returned was created
    *                from word as follows:
    *   - the word was scrambled, beginning at the
    *     first letter and continuing from left to right
    *   - two consecutive letters consisting of "A"
    *     followed by a letter that was not "A" were
    *     swapped
    *   - letters were swapped at most once
    */
   public static String scrambleWord(String word)
   {
      /* to be implemented in part a */
   }

}

如何解题

首先我们试着手算一下。

对于TAN有。

对于ABRACADABRA则有。

请试着用这种方法在草稿纸上分析剩下两个例子。

推测算法

一个个写出需要比较的字符对解题会有一定帮助,如下所示。

public class Test
{
   public static void main(String[] args)
   {
      System.out.println("ABRACADABRA".substring(0,1)); // get the A
      System.out.println("ABRACADABRA".substring(1,2)); // get the B
      // compare the A and B and swap them which results in BARACADABRA
      System.out.println("ABRACADABRA".substring(2,3)); // get the R
      System.out.println("ABRACADABRA".substring(3,4)); // get the A
      // compare the R and A and do nothing
      System.out.println("ABRACADABRA".substring(3,4)); // get the A
      System.out.println("ABRACADABRA".substring(4,5)); // get the C
      // compare the A and C and swap them which results in BARCAADABRA
      System.out.println("ABRACADABRA".substring(5,6)); // get the A
      System.out.println("ABRACADABRA".substring(6,7)); // get the D
      // compare the A and D and swap them which results in BARCADAABRA
      System.out.println("ABRACADABRA".substring(7,8)); // get the A
      System.out.println("ABRACADABRA".substring(8,9)); // get the B
      // compare the A and B and swap them which results in BARCADABARA
      System.out.println("ABRACADABRA".substring(9,10)); // get the R
      System.out.println("ABRACADABRA".substring(10,11)); // get the A
      // compare R and A and do nothing
   }
}

在这个例子中,我们从左到右遍历并比较两个相邻的字符。如果第一个字符为A而第二个不是,则把前后两个字符调换位置并增加索引跳过已经被处理的字符(否则则会把A一直调换到字符串末尾)。举例而言,如果我们交换了索引位置为01的两个字符,接下来比较的就是位置23而不是位置12。如果没有交换发生的话,索引则只增加1。以下是另一个示例。

public class Test
{
   public static void main(String[] args)
   {
      System.out.println("WHOA".substring(0,1)); // get the W
      System.out.println("WHOA".substring(1,2)); // get the H - compare the W and H and do nothing
      System.out.println("WHOA".substring(1,2)); // get the H
      System.out.println("WHOA".substring(2,3)); // get the O - compare the H and O and do nothing
      System.out.println("WHOA".substring(2,3)); // get the O
      System.out.println("WHOA".substring(3,4)); // get the A - compare the O and A and do nothing
   }
}

在这个例子中我们没有做任何交换。

代码需要循环遍历字符串并比较两个相邻字符。为了不超出索引范围,有两种方式可以进行这样的比较。一种是从索引位置0开始,循环到length() - 1为止。另一种是从索引位置1开始,循环到length()为止,此时取当前位置和前一位的字符。如果第一个字符为A而第二个字符不是A,则交换它们并让索引增加2。不交换的情况下,索引以1为单位增加。

以下是本题的参考答案。

public static String scrambleWord(String word) {
  int current = 0;
  String result = "";
  while (curent < word.length() - 1){
    if (word.substring(current, current + 1).equals("A") && !word.substring(current + 1, current + 2).equals("A")){
      result += word.substring(current + 1, current + 2);
      result += "A";
      current += 2;
    }
    else {
      result += word.substring(current, current + 1);
      current++;
    }
  }
  if (current < word.length()){
     result +=  word.substring(current);
  }
  return result;
}

陈 欣

AADPS创始人

发表评论