编码蝙蝠挑战：sameEnds

Question

CodingBat中的给定任务sameEnds：

给定一个字符串，返回出现在字符串开头和结尾且不重叠的最长子字符串。例如，sameEnds（“abXab”）是“ab”。

sameEnds("abXYab") → "ab"
sameEnds("xx") → "x"
sameEnds("xxx") → "x"

我的解决方案通过了所有测试，除了一个^：

public String sameEnds(String string) {
  String substringFront = "";
  String substringEnd = "";
  String longestSubstring = "";
  
  for (int i = 1; i < string.length() - 1; i++) {
    substringFront = string.substring(0, i);
    substringEnd = string.substring(i);
    
    if (substringEnd.contains(substringFront)) {
      longestSubstring = substringFront;
    }
  }
  
  return longestSubstring;
}

这里有什么问题？我怎样才能修复它？

Answer 1

迭代到字符串中的最后一个元素，更改循环条件可以解决问题。

for (int i = 1; i < string.length(); i++)

Answer 2

您的代码中有几个问题：

>

在到达最后一个字符之前停止迭代，而不是迭代到包含长度/2（您需要检查开头和结尾而不重叠，因此无需迭代到结尾或几乎）。

您substringEnd应该从右侧开始，因此它应该看起来像string.substring（string.length（）-i）；。

下面是一个固定的实现：

public static void main(String[] args) {
    List<String> listTest = List.of("abXYab", "xx", "xxx", "xxxx", "javaXYZjava", "javajava", "Hello! and Hello!", "x", "", "abcd", "mymmy");
    String substringFront, substringEnd, longestMatch;
    for (String string : listTest) {
        longestMatch = "";
        for (int i = 1; i <= string.length() / 2; i++) {
            substringFront = string.substring(0, i);
            substringEnd = string.substring(string.length() - i);

            if (substringEnd.equals(substringFront) && substringEnd.length() > longestMatch.length()) {
                longestMatch = substringEnd;
            }
        }

        if (!listTest.equals("")) {
            System.out.printf("%s => %s%n", string, longestMatch);
        } else {
            System.out.printf("%s => null%n", string);
        }
    }
}

以下是测试上述代码的链接：

https://www.jdoodle.com/iembed/v0/rEO

但是，为了使其更简洁，您可以使用正则表达式，它使用带有贪婪量词的捕获组在字符串的开头进行匹配，并确保在开头捕获的内容也在结尾匹配。

^(.+)(.*)\1$

这是一个测试正则表达式的链接：

https://regex101.com/r/cgowDQ/1

这可以用Java这样写：

public static void main(String[] args) {
    List<String> listTest = List.of("abXYab", "xx", "xxx", "xxxx", "javaXYZjava", "javajava", "Hello! and Hello!", "x", "", "abcd", "mymmy");
    Pattern pattern = Pattern.compile("^(.+)(.*)\\1$");
    Matcher matcher;
    for (String s : listTest) {
        matcher = pattern.matcher(s);
        if (matcher.find()) {
            System.out.printf("%s => %s%n", s, matcher.group(1));
        } else {
            System.out.printf("%s => null%n", s);
        }
    }
}

您可以在此处测试上述代码：

https://www.jdoodle.com/iembed/v0/rEK

Answer 3

除了@Dan和其他人恰当地指出的技术问题外，我还想强调不必要的复杂性问题，这在许多情况下会导致此类逻辑错误。

考虑到这一点，并考虑到这是一个挑战，我更喜欢一种极简主义的方法，如下面的方法，它不言自明，因此易于理解和调试。

public String sameEnds(String string) {
  int middle = string.length() / 2;
  for (int i = middle; i >= 0; i--) {
    String left = string.substring(0, i);
    if (string.endsWith(left)) {
      return left;
    }
  }
  return "";
}