7
A
回答
-2
使用二进制搜索。尝试比较整个字符串。如果他们不相同,尝试比较第一个字符。如果他们是平等的尝试拆分字符串(substring(0, str.length()/2
)。等等
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<minStrLen; i++){
if (s1.charAt(i) == s2.charAt(i)){
output.append(s1.charAt(i));
}else{
break;
}
}
System.out.println(output.toString());
}
}
这可能不是最佳的解决方案,但这很容易理解和编程。
我借用了merge-sort算法列表合并技术的这个思路。如果你对列表合并技术阅读不多,你会更好地理解我的算法的逻辑。
+1
你不需要一个StringBuilder,只需返回子字符串。看我的解决方案。 – dyross
1
String str1;
String str2;
// assuming str1.length > str2.length
- a.startsWith(二)==真 如果不是
- 在一个循环中保持从步骤str1和重复检查删除最后一个字符1.
26
你不需要使用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);
}
1
该解决方案适用于多种STRI ng数组。当你有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();
}
+0
你为什么使用生成器?对索引进行操作并将子字符作为结果应该足够了。 –
相关问题
- 1. 最长共同前缀属性
- 2. 最长公共后缀前缀
- 3. 最长共同后缀
- 4. 查找三元搜索树中最长的公共前缀
- 5. Java String-Collection:最长的公共前缀
- 6. 最长前缀后缀
- 7. 寻找滑动窗口中最长公共前缀的算法
- 8. 找到最长的字符串前缀
- 9. 最长的回文前缀
- 10. 最长前缀匹配
- 11. Perl - 2个或更多字符串的最长公共前缀?
- 12. 所有后缀的最长前缀字符串长度
- 13. Trie最长的前缀匹配
- 14. 渐进搜索最长前缀
- 15. 最长的回文前缀Complextity
- 16. 最长前缀匹配路由表
- 17. 使用map/reduce找到最短的唯一前缀长度
- 18. 找到包含在字典中的最长前缀
- 19. 为什么我们不使用前缀树(trie)来查找最长的公共子字符串?
- 20. 需要检查一个数字的最长前缀
- 21. 算法找到最长后缀的字符串和所述字符串的前缀之间的长度
- 22. 查找前缀字符串赋予最好的压缩
- 23. 前缀长度值为0
- 24. 使用LINQ查找通用前缀?
- 25. 查找最长的名字
- 26. 选择最长的共同TIMERANGE
- 27. 查找2个字符串的最长公共子序列?
- 28. 查找唯一最长公共子序列的数量
- 29. 在帕特里夏特里寻找最长前缀搜索的算法/步骤
- 30. 用前缀或后缀apcu_fetch()查找速度更快吗?
如果通用前缀是n,则无论如何您都需要比较前n个字符。进行二分查找是过度的,可能会导致额外的比较。 – dyross