22. 寻找最长公共前缀

墨蓝 2023-10-04 15:37 3阅读 0赞

让我们考虑以下字符串数组：

String[] texts = {"abc", "abcd", "abcde", "ab", "abcd", "abcdef"};

现在，让我们将这些字符串放在另一个下面，如下所示：

**ab**c  
**ab**cd  
**ab**cde  
**ab**  
**ab**cd  
**ab**cdef

对这些字符串的简单比较表明这ab是最长的公共前缀。 现在，让我们深入研究解决此问题的解决方案。我们在此提出的解决方案依赖于直接比较。此解决方案从数组中取出第一个字符串，并比较其余字符串中的每个字符。如果发生以下任一情况，算法将停止：

*  第一个字符串的长度大于任何其他字符串的长度
 *  第一个字符串的当前字符与任何其他字符串的当前字符不同

如果算法因为上述情况之一而被强制停止，那么最长的公共前缀是从第一个字符串到当前字符索引的从0到当前字符的索引的子字符串。否则，最长的公共前缀是数组中的第一个字符串。此解决方案的代码如下：

package Solution14;
    
    class Solution {
    	public String longestCommonPrefix(String[] strs) {
    		if (strs.length == 1) {
    			return strs[0];
    		}
    
    		int firstLen = strs[0].length();
    
    		for (int prefixLen = 0; prefixLen < firstLen; prefixLen++) {
    			char ch = strs[0].charAt(prefixLen);
    			for (int i = 1; i < strs.length; i++) {
    				if (prefixLen >= strs[i].length() || strs[i].charAt(prefixLen) != ch) {
    					return strs[i].substring(0, prefixLen);
    				}
    			}
    		}
    
    		return strs[0];
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    
    		String[] texts = { "abc", "abcd", "abcde", "ab", "abcd", "abcdef" };
    
    		System.out.println(sol.longestCommonPrefix(texts));
    	}
    
    }

此问题的其他解决方案使用众所周知的算法，例如**Binary Search**或**Trie**。在本书随附的源代码中，也有一个基于二分搜索的解决方案。