[LeetCode] 14. Longest Common Prefix

轉自LeetCode

Write a function to find the longest common prefix string amongst an array of strings.

<Solution>

這題沒什麼技巧，就逐一檢查每個字串的字元

有三個地方注意一下就好

1. 每次檢查，都針對同一個 col
2. 如果有某個 row 的長度到底了，那也代表找到 longest common prefix
3. 如果在 for 迴圈都沒有 return，就代表 strs[0] 是 longest common prefix。因為是用 strs[0] 這個 string 的長度來檢查的

code 如下

C++

	class Solution {
	public:
	string longestCommonPrefix(vector<string>& strs) {
	int const len = strs.size();
	int const strLen = (strs.empty()) ? 0 : strs[0].length();
	for(int i = 0; i < strLen; i++) {
	for(int j = 1; j < len; j++) {
	if(i == strs[j].length() || strs[0][i] != strs[j][i]) {
	return strs[0].substr(0, i);
	}
	}
	}
	//> if we reach this line
	//> means strs[0] is the shortest string
	//> and also the longest common prefix
	return (strs.empty()) ? "" : strs[0];
	}
	};

view raw longestCommonPrefix.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public String longestCommonPrefix(String[] strs) {
	final int len = strs.length;
	final int strLen = (len == 0) ? 0 : strs[0].length();
	for(int i = 0; i < strLen; i++) {
	for(int j = 1; j < len; j++) {
	if(i == strs[j].length() || strs[0].charAt(i) != strs[j].charAt(i)) {
	return strs[0].substring(0, i);
	}
	}
	}
	//> if we reach this line
	//> means strs[0] is the shortest string
	//> and also the longest common prefix
	return (len == 0) ? "" : strs[0];
	}
	}

view raw longestCommonPrefix.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun longestCommonPrefix(strs: Array<String>): String {
	val strLen = strs.firstOrNull()?.length ?: 0
	for(i in 0..strLen-1) {
	for(j in 1..strs.size-1) {
	if (i == strs[j].length || strs[0][i] != strs[j][i]) {
	return strs[0].substring(0, i)
	}
	}
	}
	return if (strLen == 0) "" else strs[0]
	}
	}

view raw longest_common_prefix.kt hosted with ❤ by GitHub