1

这个特殊的面试问题难倒了我：

Given two Strings S1 and S2. Find the longest Substring which is a Prefix of S1 and suffix of S2.

通过谷歌，我遇到了以下解决方案，但不太明白它在做什么。

public String findLongestSubstring(String s1, String s2) {
        List<Integer> occurs = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(s2.length()-1)) {
                occurs.add(i);
            }
        }

        Collections.reverse(occurs);

        for(int index : occurs) {
            boolean equals = true;
            for(int i = index; i >= 0; i--) {
                if (s1.charAt(index-i) != s2.charAt(s2.length() - i - 1)) {
                    equals = false;
                    break;
                }
            }
            if(equals) {
                return s1.substring(0,index+1);
            }
        }

        return null;
    }

我的问题：

  1. 这个解决方案是如何工作的？
    • 你如何发现这个解决方案？
  2. 有更直观/更简单的解决方案吗？
4

4 回答 4

4

您问题的第 2 部分

这是一个较短的变体：

public String findLongestPrefixSuffix(String s1, String s2) {

   for( int i = Math.min(s1.length(), s2.length()); ; i--) {
      if(s2.endsWith(s1.substring(0, i))) {
         return s1.substring(0, i);
      }
   }    
}

我Math.min用来查找最短字符串的长度，因为我不需要也不能比较更多。

someString.substring(x,y)返回从字符开始读取 someStringx并在字符处停止时获得的字符串y。我从最大可能的子字符串（s1或s2）倒退到可能的最小子字符串，即空字符串。这样，当我的条件第一次为真时，它将是最大可能的子字符串来满足它。

如果你愿意，你可以反过来，但你必须引入一个变量来保存迄今为止满足条件的最长找到的子字符串的长度：

public static String findLongestPrefixSuffix(String s1, String s2) {

   if (s1.equals(s2)) { // this part is optional and will 
      return s1;        // speed things up if s1 is equal to s2
   }                    //

   int max = 0;
   for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
      if (s2.endsWith(s1.substring(0, i))) {
         max = i;
      }
   }
   return s1.substring(0, max);
}

作为记录：您可以从i = 1后一个示例开始，以获得一点额外的性能。最重要的是，您可以使用它i来指定后缀至少要获得多长时间。;) 如果你写的Math.min(s1.length(), s2.length()) - x话，你可以用它x来指定找到的子字符串最多可以有多长。第一种解决方案也可以实现这两件事，但是最小长度涉及更多。;)

您问题的第 1 部分

在上面的部分Collections.reverse中，代码的作者搜索s1了最后一个字母s2is 的所有位置并保存了这个位置。

接下来的内容本质上是我的算法所做的，不同之处在于，他不会检查每个子字符串，而只会检查以s2.

这是某种加快速度的优化。如果速度不是那么重要，我的幼稚实现就足够了。;)

于 2013-10-20T18:59:28.327 回答
3

你在哪里找到那个解决方案？它是由可信的、受人尊敬的程序员编写的吗？如果您不确定这一点，那么它可能不值得阅读。人们可以编写非常复杂且效率低下的代码来完成非常简单的事情，并且不值得理解算法。

与其试图理解别人的解决方案，不如自己想出它更容易。我认为这样你会更好地理解问题，逻辑就变成了你自己的。随着时间的推移和练习，思维过程将开始变得更加自然。熟能生巧。

无论如何，我在这里用 Python 放了一个更简单的实现（剧透警告！）。我建议您先自己找出解决方案，然后再与我的比较。

于 2013-10-19T22:43:19.427 回答
2

Apache commons lang3， StringUtils.getCommonPrefix()

Java 在通过 stdlib 提供有用的东西方面真的很糟糕。从好的方面来说，Apache 几乎总是有一些合理的工具。

于 2016-04-12T12:01:31.450 回答
0

我将@TheMorph 的答案转换为javascript。希望这对 js 开发者有帮助

if (typeof String.prototype.endsWith !== 'function') {
    String.prototype.endsWith = function(suffix) {
        return this.indexOf(suffix, this.length - suffix.length) !== -1;
    };
}

function findLongestPrefixSuffix(s2, s1) {

   for( var i = Math.min(s1.length, s2.length); ; i--) {
      if(s2.endsWith(s1.substring(0, i))) {
         return s1.substring(0, i);
      }
   }    
}

console.log(findLongestPrefixSuffix('abc', 'bcd')); // result: 'bc'
于 2018-11-20T04:24:59.760 回答