如何修复CodingBat中的递归代码错误？

Question

所以，我在 CodingBat 上解决了这个问题

Given a string, compute recursively (no loops) a new string where all appearances of "pi" have been replaced by "3.14".

changePi("xpix") → "x3.14x"

changePi("pipi") → "3.143.14"

changePi("pip") → "3.14p"

这是我的代码：

public String changePi(String str) {
    if (str.length() < 2)
        return str;
    char c1 = str.charAt(0);
    char c2 = str.charAt(1);
    if (c1 == 'p' && c2 == 'i')
        return "3.14" + changePi(str.substring(2));
    return c1 + c2 + changePi(str.substring(2));
}

此代码不适用于许多测试用例，如下图所示

我无法理解我的递归代码有什么问题以及为什么会显示这样的输出。谁能帮我理解我做错了什么？

Answer 1

您的解决方案需要稍作调整 – 当您找到 p 和 i 在一起时，您正确地向前跳过 2 个字符以查看字符串的其余部分 – 您是return "3.14" + changePi(str.substring(2));.

但是，当您 not 一起找到 p 和 i 时，您需要更改逻辑以仅向前跳过一个字符而不是二。所以不是这个：

return c1 + c2+ changePi(str.substring(2));

这样做：

return c1 + changePi(str.substring(1));

进行更改后，我得到以下输出（使用您的每个输入）与您的预期输出相匹配：

x3.14x
3.143.14
3.14p
3.14
hip
p
x

3.14xx
xyzzy

Answer 2

这里有几个解决问题的方法。第二个类似于你的方法。在第一个中，我最初包含了一个目标替换文本，所以我需要确定它的长度。因此 "pi".length() 使用，因为我决定保留它。


       public static void main(String[] args) {
          String[] tests = {
                "piabcpiefgpi", "xxxxxxpix", "xpix", "pip", "3.14", "3.14p",
                "hip", "p", "x", "", "pixx", "xyzzy"
          };
          for (String t : tests) {
             System.out.println(t + " --> " + replaceV2(t));
          }
       }

       public static String replaceV1(String a) {
          int i = a.indexOf("pi");
          if (i < 0) {
             return a;
          }
          return replaceV1(
                a.substring(0, i) + "3.14" + a.substring(i + "pi".length()));
       }

       public static String replaceV2(String a) {
          if (a.length() < 2) {
             return a;
          }

          if (a.startsWith("pi")) {
             a = "3.14" + replaceV2(a.substring(2));
          }
          return a.substring(0, 1) + replaceV2(a.substring(1));
       }
    }

他们都打印了以下内容。

piabcpiefgpi --> 3.14abc3.14efg3.14
xxxxxxpix --> xxxxxx3.14x
xpix --> x3.14x
pip --> 3.14p
3.14 --> 3.14
3.14p --> 3.14p
hip --> hip
p --> p
x --> x
 --> 
pixx --> 3.14xx
xyzzy --> xyzzy

Answer 3

'''  change pi to 3.14 python code'''

def changePi(s):
    if len(s) == 2 and s == 'pi' :  return '3.14'
    if len(s) <= 2 :  return s 
    chars , sub = s[0:2] , s[1:]
    if chars == 'pi':
       chars = '3.14'
       sub = sub[1:]
    else:  chars =  chars[0]
    return chars + changePi(sub) 

print changePi("xpix") 
print changePi("pipi") 
print changePi("pip")

如何修复CodingBat中的递归代码错误？

How to fix the recursive code error in CodingBat?

java

recursion

runtime-error

testcase