1.题目描述

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.
Note:

All given inputs are in lowercase letters a-z.

题目的意思就是求最长公共前缀。

2.解法

思路就是用第一个字符串（定义为 first）跟其他字符串去比较。是否存在最长公共前缀，开始先假定公共字符串是first，判断是否是其他字符串里的前缀，不匹配时，first减少一个字符，继续比较，当first为空时，那么就不存在最长公共字符串。

/**
	 * 求最长公共前缀
	 *
	 * @param strs
	 * @return
	 */
	public static String longestCommonPrefix(String[] strs) {
		if (strs.length <=0) {
			return "";
		}

		String first = strs[0];
		for (int i = 1; i < strs.length; i++) {

			while (strs[i].indexOf(first) != 0) {
				first = first.substring(0, first.length() - 1);
			}
		}
		return first;
	}

执行结果：

这道题变更一下，如果要求最长公共字符串，该怎么做呢？其实就是看在其他字符中是否存在first，不必要考虑是否是前缀匹配，不断减少first的字符去比较。

/**
	 * 求最长公共字符
	 * @param strs
	 * @return
	 */
	public static String longestCommon(String[] strs) {
		if (strs.length <=0) {
			return "";
		}

		String first = strs[0];
		for (int i = 1; i < strs.length; i++) {
			while (!strs[i].contains(first)) {
				first = first.substring(0, first.length() - 1);
			}
		}
		return first;
	}

如果不使用JDK提供的indexOf、subString功能，改如何做呢？