【LeetCode 14. Longest Common Prefix】（最长公共前缀，indexOf or sort）

【LeetCode 14. Longest Common Prefix】（最长公共前缀，indexOf or sort）

题目链接 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “”. Example 1: Input: [“flower”,”flow”,”flight”] Output: “fl” Example 2: Input: [“dog”,”racecar”,”car”] Output: “” Explanation: There is no common prefix among the input strings. 思路： 1. 判断是否是公共前缀，高效解法可以构建Trie树，这里使用indexOf()判断子串第一次出现的位置是否为0 Code： import java.util.HashMap; public class Solution { public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; String prefix = strs[0]; for (int i = 1; i < strs.length; i++) { while (strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() - 1); } } return prefix; } public static void main(String[] args) { String strs[] = { "flower", "flow", "flight" }; String reString = new Solution().longestCommonPrefix(strs); System.out.println(reString); } } 2 sort排序，直接比较第一个字符串与最后一个字符串的公共子串。 import java.util.Arrays; import java.util.HashMap; public class Solution { public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; Arrays.sort(strs); StringBuffer reStringBuffer = new StringBuffer(); char[] a = strs[0].toCharArray(); char[] b = strs[strs.length - 1].toCharArray(); for (int i = 0; i < a.length; i++) { if (b.length > i && b[i] == a[i]) { reStringBuffer.append(b[i]); } else { break; } } return reStringBuffer.toString(); } public static void main(String[] args) { String strs[] = { "flower", "flow", "flight" }; String reString = new Solution().longestCommonPrefix(strs); System.out.println(reString); } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。