找到最长的公共前缀?
在两个字符串中:
“玛丽有只小羊羔”
“玛丽有一只大羔羊”
应该回来
“玛丽有一个”
您不需要使用StringBuilder
– 只需返回子字符串:
public String greatestCommonPrefix(String a, String b) { int minLength = Math.min(a.length(), b.length()); for (int i = 0; i < minLength; i++) { if (a.charAt(i) != b.charAt(i)) { return a.substring(0, i); } } return a.substring(0, minLength); }
String str1; String str2; // assuming str1.length > str2.length
- a.startsWith(b)==如果不是,则为true
- 在循环中继续从str1删除最后一个char并重复检查步骤1。
public class Test{ public static void main(String[] args){ String s1 = "Mary Had a Little Lamb"; String s2 = "Mary Had a Big Lamb"; int minStrLen = s1.length(); if ( minStrLen > s2.length()){ minStrLen = s2.length(); } StringBuilder output = new StringBuilder(); for(int i=0; i
这可能不是最佳解决方案,但这很容易理解和编程。
我从合并排序算法的列表合并技术中借鉴了这个想法。 如果您对列表合并技术一无所知,您将更好地理解我的算法的逻辑。
此解决方案应用于多字符串数组。 当你有3或4个字符串时,最好使用StringBuilder。 对于2个字符串,可以使用子字符串。 C#中的代码:
public string LongestCommonPrefix(string[] strs) { if(strs.Length == 0) return string.Empty; Array.Sort(strs); var first = strs[0]; var last = strs[strs.Length - 1]; var sb = new StringBuilder(); for(int i = 0; i< first.Length; i++) { if(first[i] != last[i]) { break; } sb.Append(first[i]); } return sb.ToString(); }
Apache Commons拯救!
org.apache.commons.lang3.StringUtils.getCommonPrefix
…并将源代码与dyross的巧妙/勇敢的努力进行比较(目前投票率最高)。 但她/他的代码虽然很好,却只处理两个String
。 这可以处理任何数字。
除了不重新发明轮子之外,我还能想到使用Apache Commons总是最适合这种事情的两个原因。
- 可以指望Apache工程师开发出经过全面测试的代码来处理任何陷阱
- 这意味着您不会使用stoopid实用程序方法混乱您的漂亮代码。 相反,你可以继续使用这些有趣的东西。
如果整个给定的Apache Commons模块对于您的上下文来说真的太多了(它们通常只有几KB,但可以),您可以从源代码中提取所需的位(假设这符合许可证)。 在这种情况下, indexOfDifference是一个必不可少的function……
使用二进制搜索。 尝试比较整个字符串。 如果它们不相等,请尝试比较第一个字符。 如果它们相等则尝试拆分字符串( substring(0, str.length()/2
)。等等。