C++實(shí)現(xiàn)LeetCode(14.最長(zhǎng)共同前綴)

更新時(shí)間：2021年07月13日 09:09:33 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(14.最長(zhǎng)共同前綴),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 14. Longest Common Prefix 最長(zhǎng)共同前綴

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.

這道題讓我們求一系列字符串的共同前綴，沒(méi)有什么特別的技巧，無(wú)腦查找即可，定義兩個(gè)變量i和j，其中i是遍歷搜索字符串中的字符，j是遍歷字符串集中的每個(gè)字符串。這里將單詞上下排好，則相當(dāng)于一個(gè)各行長(zhǎng)度有可能不相等的二維數(shù)組，遍歷順序和一般的橫向逐行遍歷不同，而是采用縱向逐列遍歷，在遍歷的過(guò)程中，如果某一行沒(méi)有了，說(shuō)明其為最短的單詞，因?yàn)楣餐熬Y的長(zhǎng)度不能長(zhǎng)于最短單詞，所以此時(shí)返回已經(jīng)找出的共同前綴。每次取出第一個(gè)字符串的某一個(gè)位置的單詞，然后遍歷其他所有字符串的對(duì)應(yīng)位置看是否相等，如果有不滿(mǎn)足的直接返回 res，如果都相同，則將當(dāng)前字符存入結(jié)果，繼續(xù)檢查下一個(gè)位置的字符，參見(jiàn)代碼如下：

C++ 解法一：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        string res = "";
        for (int j = 0; j < strs[0].size(); ++j) {
            char c = strs[0][j];
            for (int i = 1; i < strs.size(); ++i) {
                if (j >= strs[i].size() || strs[i][j] != c) {
                    return res;
                }
            }
            res.push_back(c);
        }
        return res;
    }
};

Java 解法一：

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String res = new String();
        for (int j = 0; j < strs[0].length(); ++j) {
            char c = strs[0].charAt(j);
            for (int i = 1; i < strs.length; ++i) {
                if (j >= strs[i].length() || strs[i].charAt(j) != c) {
                    return res;
                }
            }
            res += Character.toString(c);
        }
        return res;
    }
}

我們可以對(duì)上面的方法進(jìn)行適當(dāng)精簡(jiǎn)，如果發(fā)現(xiàn)當(dāng)前某個(gè)字符和第一個(gè)字符串對(duì)應(yīng)位置的字符不相等，說(shuō)明不會(huì)再有更長(zhǎng)的共同前綴了，直接通過(guò)用 substr 的方法直接取出共同前綴的子字符串。如果遍歷結(jié)束前沒(méi)有返回結(jié)果的話(huà)，說(shuō)明第一個(gè)單詞就是公共前綴，返回為結(jié)果即可。代碼如下：

C++ 解法二：

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

Java 解法二：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        for (int j = 0; j < strs[0].length(); ++j) {
            for (int i = 0; i < strs.length; ++i) {
                if (j >= strs[i].length() || strs[i].charAt(j) != strs[0].charAt(j)) {
                    return strs[i].substring(0, j); 
                }   
            }
        }
        return strs[0];
    }
}

我們?cè)賮?lái)看一種解法，這種方法給輸入字符串?dāng)?shù)組排了個(gè)序，想想這樣做有什么好處？既然是按字母順序排序的話(huà)，那么有共同字母多的兩個(gè)字符串會(huì)被排到一起，而跟大家相同的字母越少的字符串會(huì)被擠到首尾兩端，那么如果有共同前綴的話(huà)，一定會(huì)出現(xiàn)在首尾兩端的字符串中，所以只需要找首尾字母串的共同前綴即可。比如例子1排序后為 ["flight", "flow", "flower"]，例子2排序后為 ["cat", "dog", "racecar"]，雖然例子2沒(méi)有共同前綴，但也可以認(rèn)為共同前綴是空串，且出現(xiàn)在首尾兩端的字符串中。由于是按字母順序排的，而不是按長(zhǎng)度，所以首尾字母的長(zhǎng)度關(guān)系不知道，為了防止溢出錯(cuò)誤，只遍歷而這種較短的那個(gè)的長(zhǎng)度，找出共同前綴返回即可，參見(jiàn)代碼如下：

C++ 解法三：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        sort(strs.begin(), strs.end());
        int i = 0, len = min(strs[0].size(), strs.back().size());
        while (i < len && strs[0][i] == strs.back()[i]) ++i;
        return strs[0].substr(0, i);
    }
};

Java 解法三：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        Arrays.sort(strs);
        int i = 0, len = Math.min(strs[0].length(), strs[strs.length - 1].length());
        while (i < len && strs[0].charAt(i) == strs[strs.length - 1].charAt(i)) i++;
        return strs[0].substring(0, i);
    }
}

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(14.最長(zhǎng)共同前綴)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)最長(zhǎng)共同前綴內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: