14. 最长公共前缀

题目描述

输入字符串数组 strs。前缀是从字符串开头起的一段连续字符。

返回所有字符串共同拥有的最长前缀。如果它们没有任何共同前缀，返回空字符串 ""。

示例 1

输入：strs = ["flower","flow","flight"]
输出："fl"

解释：三个字符串都以 "fl" 开头，第三个字符就不再相同。

示例 2

输入：strs = ["dog","racecar","car"]
输出：""

解释：三个字符串的首字母各不相同，没有公共前缀。

数据范围

1 <= strs.length <= 200
0 <= strs[i].length <= 200
非空的 strs[i] 只含小写英文字母。

解题思路：纵向扫描

纵向扫描：把所有字符串上下对齐，一列一列地比较。以第一个字符串为基准，对第 j 列检查其余每个字符串：如果某个字符串已经结束，或者它的第 j 个字符与基准不同，前 j 个字符就是答案。如果基准的每一列都通过，答案就是基准本身。

为什么正确

开始检查第 j 列时，first[:j] 一定是所有字符串的公共前缀。

复杂度分析

时间 O(S)，S 是所有字符串的总长度（实际只比较到第一处不同）；空间 O(1)。

易错点

要先判断 j == len(s)（其他字符串比基准短），再访问 s[j]，否则会越界。如果整个基准都是公共前缀，循环正常结束，别忘了在末尾返回 first。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        first = strs[0]
        for j in range(len(first)):
            for s in strs[1:]:
                if j == len(s) or s[j] != first[j]:
                    return first[:j]
        return first

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String first = strs[0];
        for (int j = 0; j < first.length(); j++) {
            for (int k = 1; k < strs.length; k++) {
                String s = strs[k];
                if (j == s.length() || s.charAt(j) != first.charAt(j)) {
                    return first.substring(0, j);
                }
            }
        }
        return first;
    }
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        const string& first = strs[0];
        for (int j = 0; j < (int)first.size(); j++) {
            for (int k = 1; k < (int)strs.size(); k++) {
                const string& s = strs[k];
                if (j == (int)s.size() || s[j] != first[j]) {
                    return first.substr(0, j);
                }
            }
        }
        return first;
    }
};

func longestCommonPrefix(strs []string) string {
	first := strs[0]
	for j := 0; j < len(first); j++ {
		for _, s := range strs[1:] {
			if j == len(s) || s[j] != first[j] {
				return first[:j]
			}
		}
	}
	return first
}

var longestCommonPrefix = function(strs) {
    const first = strs[0];
    for (let j = 0; j < first.length; j++) {
        for (let k = 1; k < strs.length; k++) {
            const s = strs[k];
            if (j === s.length || s[j] !== first[j]) {
                return first.slice(0, j);
            }
        }
    }
    return first;
};

function longestCommonPrefix(strs: string[]): string {
    const first = strs[0];
    for (let j = 0; j < first.length; j++) {
        for (let k = 1; k < strs.length; k++) {
            const s = strs[k];
            if (j === s.length || s[j] !== first[j]) {
                return first.slice(0, j);
            }
        }
    }
    return first;
}

载入编辑器，自己跑一遍 →

其他解法

纵向扫描遇到第一个不同字符就停止，实际最快；字典序法把问题归结到两个串；二分法利用单调性但多一个 log。

解法 2：字典序最小与最大串时间 O(S)，空间 O(1)

按字典序，所有字符串的公共前缀等于字典序最小串和最大串的公共前缀：字典序介于两者之间的串必然也以这个前缀开头。一次遍历找到最小和最大串，再逐字符比较这两个串。

只需比较两个串，思路巧妙，可以练习利用字典序的性质。求最小/最大串时的字符串比较仍然要扫描字符，最坏情况下与纵向扫描同阶。正确性依赖字典序性质，需要理解后才敢用。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        lo, hi = min(strs), max(strs)
        i = 0
        while i < len(lo) and lo[i] == hi[i]:
            i += 1
        return lo[:i]

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String lo = strs[0], hi = strs[0];
        for (String s : strs) {
            if (s.compareTo(lo) < 0) lo = s;
            if (s.compareTo(hi) > 0) hi = s;
        }
        int i = 0;
        while (i < lo.length() && lo.charAt(i) == hi.charAt(i)) i++;
        return lo.substring(0, i);
    }
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string lo = *min_element(strs.begin(), strs.end());
        string hi = *max_element(strs.begin(), strs.end());
        int i = 0;
        while (i < (int)lo.size() && lo[i] == hi[i]) i++;
        return lo.substr(0, i);
    }
};

func longestCommonPrefix(strs []string) string {
	lo, hi := strs[0], strs[0]
	for _, s := range strs {
		if s < lo {
			lo = s
		}
		if s > hi {
			hi = s
		}
	}
	i := 0
	for i < len(lo) && lo[i] == hi[i] {
		i++
	}
	return lo[:i]
}

var longestCommonPrefix = function(strs) {
    let lo = strs[0], hi = strs[0];
    for (const s of strs) {
        if (s < lo) lo = s;
        if (s > hi) hi = s;
    }
    let i = 0;
    while (i < lo.length && lo[i] === hi[i]) i++;
    return lo.substring(0, i);
};

function longestCommonPrefix(strs: string[]): string {
    let lo = strs[0], hi = strs[0];
    for (const s of strs) {
        if (s < lo) lo = s;
        if (s > hi) hi = s;
    }
    let i = 0;
    while (i < lo.length && lo[i] === hi[i]) i++;
    return lo.substring(0, i);
};

解法 3：二分前缀长度时间 O(S·log m)，空间 O(1)

若长度 L 的前缀是公共前缀，则更短的也是，满足单调性。在 [0, 最短串长度 m] 上二分 L：检查所有字符串是否都以 strs[0] 的前 L 个字符开头，成立则向右找，否则向左找。

展示了「对答案二分」的通用思路。但每次检查都要扫描大量字符，总体比纵向扫描多一个 log 因子，实际更慢。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def ok(length):
            prefix = strs[0][:length]
            return all(s.startswith(prefix) for s in strs)

        lo, hi = 0, min(len(s) for s in strs)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if ok(mid):
                lo = mid
            else:
                hi = mid - 1
        return strs[0][:lo]

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int lo = 0, hi = Integer.MAX_VALUE;
        for (String s : strs) hi = Math.min(hi, s.length());
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (ok(strs, mid)) lo = mid;
            else hi = mid - 1;
        }
        return strs[0].substring(0, lo);
    }

    private boolean ok(String[] strs, int len) {
        String prefix = strs[0].substring(0, len);
        for (String s : strs)
            if (!s.startsWith(prefix)) return false;
        return true;
    }
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int lo = 0, hi = INT_MAX;
        for (auto& s : strs) hi = min(hi, (int)s.size());
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (ok(strs, mid)) lo = mid;
            else hi = mid - 1;
        }
        return strs[0].substr(0, lo);
    }

    bool ok(vector<string>& strs, int len) {
        for (auto& s : strs)
            if (s.compare(0, len, strs[0], 0, len) != 0) return false;
        return true;
    }
};

func longestCommonPrefix(strs []string) string {
	ok := func(length int) bool {
		prefix := strs[0][:length]
		for _, s := range strs {
			if s[:length] != prefix {
				return false
			}
		}
		return true
	}
	lo, hi := 0, len(strs[0])
	for _, s := range strs {
		hi = min(hi, len(s))
	}
	for lo < hi {
		mid := (lo + hi + 1) / 2
		if ok(mid) {
			lo = mid
		} else {
			hi = mid - 1
		}
	}
	return strs[0][:lo]
}

var longestCommonPrefix = function(strs) {
    const ok = (len) => {
        const prefix = strs[0].substring(0, len);
        return strs.every(s => s.startsWith(prefix));
    };
    let lo = 0, hi = Math.min(...strs.map(s => s.length));
    while (lo < hi) {
        const mid = Math.floor((lo + hi + 1) / 2);
        if (ok(mid)) lo = mid;
        else hi = mid - 1;
    }
    return strs[0].substring(0, lo);
};

function longestCommonPrefix(strs: string[]): string {
    const ok = (len: number): boolean => {
        const prefix = strs[0].substring(0, len);
        return strs.every(s => s.startsWith(prefix));
    };
    let lo = 0, hi = Math.min(...strs.map(s => s.length));
    while (lo < hi) {
        const mid = Math.floor((lo + hi + 1) / 2);
        if (ok(mid)) lo = mid;
        else hi = mid - 1;
    }
    return strs[0].substring(0, lo);
};

字符串专题的其他题目

查看字符串全部题目 →