java - Google Foobar，字符串清理，测试失败 5

Question

我正在接受这个 Google 挑战，目前处于第 3 级。这个问题称为字符串清理。

你的 spy Beta Rabbit 成功潜入了一个由疯狂科学家组成的实验室，他们正在把兔子变成僵尸。他向你发送了一条文本传输，但被盗版者截获了，他通过多次在文本中重复插入相同的词来混淆消息。在每一步，他可能在任何地方插入这个词，包括在开头或结尾，或者甚至是他在上一步中插入的单词的副本。通过给海盗一个达布隆，你让他告诉你那个词是什么。几瓶朗姆酒后，他还告诉你原始文本是通过重复删除该词而形成的最短的字符串，并且该文本实际上是所有可能的字典中最早的字符串最短的候选人。使用此信息，您能算出您的 spy 最初发送的是什么消息吗？

例如，如果最后的文本 block 是“lolol”，插入的单词是“lol”，则最短的可能字符串是“ol”(从中删除“lol”开头)和“lo”(从末尾删除“lol”)。因此，原文一定是“lo”，这是字典上最早的字符串。

编写一个名为 answer(chunk, word) 的函数，该函数返回最短的、按字典顺序排列最早的字符串，该字符串可以通过从 block 中删除单词的出现而形成。请记住，事件可能是嵌套的，删除一个事件可能会导致另一个事件。例如，从“aabb”中删除“ab”会导致另一个“ab”不是原本存在。另请记住，您的 spy 的原始消息可能是一个空字符串。

chunk 和 word 将只包含小写字母 [a-z]。 block 将不超过 20 个字符。word 至少有一个字符，且不超过 chunk 中的字符数。

测试用例

输入: (字符串) block =“lololololo” (字符串)字=“哈哈”输出: (字符串)“looo”

输入: (字符串) block =“goodgooogoogfogoood” (字符串)字=“咕”输出: (字符串)“dogfood”

这是我的代码:

public class Answer {   
public static String answer(String chunk, String word)
{
    if (compareString(chunk, word)) return "";
    String s1 = checkBack(chunk, word);
    String s2 = checkFront(chunk, word);
    if (s2.length() < s1.length()) return s2;
    else return s1;
}

private static String checkBack(String chunk, String word)
{
    if (compareString(chunk, word)) return "";
    if (chunk.length() <= word.length()) return chunk;
    for (int i = chunk.length(); i >= word.length(); i--)
    {
        if (compareString(chunk.substring(i-word.length(), i), word))
        {
            return checkBack(removeAt(i-word.length(), i-1, chunk), word);
        }
    }
    return chunk;
}

private static String checkFront(String chunk, String word)
{
    if (compareString(chunk, word)) return "";
    if (chunk.length() <= word.length()) return chunk;
    for (int i = 0; i < chunk.length()-word.length(); i++)
    {
        if (compareString(chunk.substring(i, word.length()+i), word))
        {
            return checkFront(removeAt(i, word.length()+i-1, chunk), word);
        }
    }
    return chunk;
}

private static String removeAt(int startIndex, int endIndex, String input)
{
   if (endIndex+1 == input.length())
   {
       return input.substring(0, startIndex);
   }
   else 
   {
      return input.substring(0, startIndex) + input.substring(endIndex+1);
   }
 }

 private static boolean compareString(String s1, String s2)
 {
   char[] c1 = s1.toCharArray();
   char[] c2 = s2.toCharArray();
   if (c1.length != c2.length) return false;
   for (int i = 0; i < c1.length; i++)
   {
       if (c1[i] != c2[i]) return false;      
   }
   return true;
 }

我的代码通过了前四项测试，但未能通过测试 5。我进行了相当多的测试，但没有找到导致测试失败的任何可能原因。请看一下，看看您是否可以找到更多测试它的方法或它未通过测试的任何可能原因 5. 感谢您的帮助!

更新我已经根据 Ken 提出的测试用例修改了我的代码。我通过了他的测试用例，但仍然没有通过测试 5。

Answer 1

1. 在函数中 CheckFront , 你只对 CheckFront 做递归, 而不是 CheckFront和 CheckBack

2. 同CheckBack

3. 递归太多，因此函数调用太多，这在 Google Foobar 中会非常慢。我认为迭代要好得多(这是我使用的)。

4. 如果两个字符串长度相同，但 s2 是“lo”而 s1 是“ol”怎么办。我认为你混淆了词法顺序和长度

   (s2.length() < s1.length()) return s2;
   else return s1;
   

5. 如果你有一个特殊的情况，你必须先删除中间的单词才能得到正确的结果。