[算法]最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。

示例

输入: [“flower”,“flow”,“flight”] 输出: “fl”

输入: [“dog”,“racecar”,“car”] 输出: “” 解释: 输入不存在公共前缀。

这是一道简单题，没什么说的

class Solution { public String longestCommonPrefix(String[] str) { if(str==null||str.length==0) return ""; //随便取第一个开始，这里其实也可以取长度最短的一个 String result = str[0]; for (String s : str) { int j = 0; //下标必须同时小于result和当前字符串的长度 for (; j < result.length() && j < s.length(); j++) { if (result.charAt(j) != s.charAt(j)) { break; } } //对result截取公共部分 result = result.substring(0, j); } return result; } }

举一反三

思考，如果不是公共前缀了，而是子集，中间的某几个字符相同，如何处理？ 这就涉及到动态规划的LCS最长公共子序列，中级了，后面我学会了再记录 。