亚洲理论在线A中文字幕,国产精品久久中文字幕,狠狠做五月深爱婷婷天天综合

【經典算法】LeetCode14:最長公共前綴(Java/C/Python3實現含注釋說明，Easy)

標簽：字符串處理、前綴判斷

題目

編寫一個函數來查找字符串數組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 ""。

示例 1：

輸入：strs = ["flower","flow","flight"]
輸出："fl"
示例 2：

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。
提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 僅由小寫英文字母組成

原題：LeetCode 14

思路及實現

方式一：橫向掃描

思路

代碼實現

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串數組為空或者長度為0，則返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 將第一個字符串作為前綴進行初始化
        String prefix = strs[0];

        // 數組中字符串的數量
        int count = strs.length;

        // 遍歷字符串數組，依次求取最長公共前綴
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);

            // 如果最長公共前綴為空，則可以提前結束循環
            if (prefix.length() == 0) {
                break;
            }
        }

        // 返回最長公共前綴
        return prefix;
    }

    // 求取兩個字符串的最長公共前綴
    public String longestCommonPrefix(String str1, String str2) {
        // 獲取兩個字符串的最小長度
        int length = Math.min(str1.length(), str2.length());

        // 初始化索引
        int index = 0;

        // 遍歷兩個字符串，找到最長公共前綴的結束索引
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }

        // 返回最長公共前綴
        return str1.substring(0, index);
    }
}

說明：
首先，通過判斷字符串數組strs是否為空或長度為0，來確定是否存在最長公共前綴。如果數組為空或長度為0，則直接返回空字符串。
將字符串數組中的第一個字符串作為初始化的最長公共前綴prefix。
使用一個循環遍歷剩余的字符串，依次計算最長公共前綴。在每次循環中，調用longestCommonPrefix()方法，將當前最長公共前綴prefix和當前遍歷的字符串進行比較，更新最長公共前綴。
如果最長公共前綴為空字符串，則說明不存在公共前綴，無需繼續循環，直接跳出。最后，返回最長公共前綴prefix。
longestCommonPrefix()方法是一個內部方法，用于找到兩個字符串str1和str2的最長公共前綴。
首先，獲取兩個字符串的最小長度length。初始化索引index為0。
遍歷兩個字符串，比較對應位置的字符是否相等，直到遇到不相等的字符或到達較短字符串的末尾。
最后，返回前綴部分的字符串，即str1中的前index個字符。

C語言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串數組為空或者長度為0，則返回空字符串
    if (strs == NULL || strsSize == 0)
        return "";

    // 將第一個字符串作為初始的最長公共前綴
    char* prefix = strs[0];

    // 遍歷數組剩余的字符串，更新最長公共前綴
    for (int i = 1; i < strsSize; i++) {
        prefix = lcp(prefix, strs[i]);
        
        // 如果最長公共前綴為空，則跳出循環
        if (prefix[0] == '\0')
            break;
    }
    
    return prefix;
}

說明：
longestCommonPrefix() 函數用于找到字符串數組 strs 中的最長公共前綴。
首先，判斷字符串數組是否為空或長度為0，如果是，則直接返回空字符串。將數組的第一個字符串作為初始的最長公共前綴 prefix。
遍歷數組剩余的字符串，調用 lcp() 函數計算當前字符串與當前最長公共前綴的公共前綴，并更新最長公共前綴 prefix。
如果最長公共前綴為空字符串，則無需繼續遍歷，跳出循環。返回最長公共前綴 prefix。 lcp() 函數用于找到兩個字符串 str1 和str2 的最長公共前綴。獲取兩個字符串的最小長度 length。初始化索引 index 為0。
遍歷兩個字符串，比較對應位置的字符是否相等，直到遇到不相等的字符或到達較短字符串的末尾。創建一個新的字符串來存儲最長公共前綴commonPrefix。
使用 strncpy() 函數從 str1 復制 index 個字符到 commonPrefix 中。在
commonPrefix 的末尾添加字符串結束符 ‘\0’。返回最長公共前綴 commonPrefix。

Python3版本

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 如果字符串數組為空，則返回空字符串
        if not strs:
            return ""
        
        # 將數組的第一個字符串作為初始的最長公共前綴
        prefix, count = strs[0], len(strs)
        
        # 遍歷數組剩余的字符串，更新最長公共前綴
        for i in range(1, count):
            prefix = self.lcp(prefix, strs[i])
            
            # 如果最長公共前綴為空，則跳出循環
            if not prefix:
                break
        
        return prefix
    
    # 求取兩個字符串的最長公共前綴
    def lcp(self, str1, str2):
        # 獲取兩個字符串的最小長度
        length, index = min(len(str1), len(str2)), 0
        
        # 遍歷兩個字符串，找到最長公共前綴的結束索引
        while index < length and str1[index] == str2[index]:
            index += 1
        
        # 返回最長公共前綴
        return str1[:index]

說明：
longestCommonPrefix()方法是一個類方法，用于找到字符串數組strs中的最長公共前綴。
首先，判斷字符串數組是否為空，如果為空，則直接返回空字符串。將數組的第一個字符串作為初始的最長公共前綴 prefix。
獲取數組中的字符串數量 count。使用一個循環遍歷剩余的字符串，調用 lcp()
方法來計算當前字符串與當前最長公共前綴的公共前綴，并更新最長公共前綴 prefix。如果最長公共前綴為空字符串，則無需繼續遍歷，跳出循環。
返回最長公共前綴 prefix。 lcp() 方法是一個類方法，用于找到兩個字符串 str1 和 str2 的最長公共前綴。
獲取兩個字符串的最小長度 length。初始化索引 index 為0。
遍歷兩個字符串，比較對應位置的字符是否相等，直到遇到不相等的字符或到達較短字符串的末尾。返回前綴部分的字符串，即 str1 中的前
index 個字符。

復雜度分析

時間復雜度：O(mn)，其中 m 是字符串數組中的字符串的平均長度，n 是字符串的數量。最壞情況下，字符串數組中的每個字符串的每個字符都會被比較一次。
空間復雜度：O(1)。使用的額外空間復雜度為常數。

方式二：縱向掃描

思路

方法一是橫向掃描，依次遍歷每個字符串，更新最長公共前綴。另一種方法是縱向掃描。縱向掃描時，從前往后遍歷所有字符串的每一列，比較相同列上的字符是否相同，如果相同則繼續對下一列進行比較，如果不相同則當前列不再屬于公共前綴，當前列之前的部分為最長公共前綴。

代碼實現

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串數組為空或者長度為0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 獲取第一個字符串的長度和數組的長度
        int length = strs[0].length();
        int count = strs.length;

        // 遍歷第一個字符串的每個字符
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);

            // 遍歷剩余的字符串進行比較
            for (int j = 1; j < count; j++) {
                // 如果當前字符已經超過了某個字符串的長度，或者當前字符不等于其他字符串對應位置的字符，返回前綴部分
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }

        // 返回第一個字符串作為最長公共前綴
        return strs[0];
    }
}

說明：
longestCommonPrefix() 方法用于尋找字符串數組 strs 中的最長公共前綴。
如果字符串數組為空或長度為0，直接返回空字符串。獲取第一個字符串的長度和字符串數組的長度。遍歷第一個字符串的每個字符。獲取當前字符
c，用來與其他字符串的對應位置字符進行比較。遍歷剩余的字符串，依次比較當前字符和其他字符串對應位置的字符。
如果當前字符已經超過了某個字符串的長度，或者當前字符不等于其他字符串對應位置的字符，返回前綴部分，即第一個字符串的從索引0到當前位置的子串。
返回第一個字符串作為最長公共前綴，因為該字符串是其他字符串的公共前綴。

C語言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 函數聲明
char* longestCommonPrefix(char** strs, int strsSize);
char* commonPrefix(char* str1, char* str2);

/**
int main() {
    char* strs[] = {"flower", "flow", "flight"};
    int strsSize = 3;

    char* result = longestCommonPrefix(strs, strsSize);
    printf("Longest Common Prefix: %s\n", result);

    // 釋放內存
    free(result);

    return 0;
}
**/
/*
 * 獲取字符串數組中的最長公共前綴
 * 參數: strs - 字符串數組, strsSize - 字符串數組的大小
 * 返回值: 最長公共前綴的指針
 */
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串數組為空或者大小為0，直接返回空字符串
    if (strs == NULL || strsSize == 0) {
        return "";
    }

    // 字符串數組的第一個字符串
    char* firstStr = strs[0];

    // 獲取第一個字符串的長度
    int length = strlen(firstStr);

    // 遍歷第一個字符串的每個字符
    for (int i = 0; i < length; i++) {
        char c = firstStr[i];
        
        // 遍歷剩余的字符串進行比較
        for (int j = 1; j < strsSize; j++) {
            // 如果當前字符已經超過了某個字符串的長度，或者當前字符不等于其他字符串對應位置的字符，返回前綴部分
            if (i >= strlen(strs[j]) || strs[j][i] != c) {
                char* prefix = (char*)malloc((i + 1) * sizeof(char));
                strncpy(prefix, firstStr, i);
                prefix[i] = '\0';
                return prefix;
            }
        }
    }

    // 返回第一個字符串作為最長公共前綴
    return strdup(firstStr);
}

/*
 * 獲取兩個字符串的最長公共前綴的公共前綴
 * 參數: str1 - 字符串1, str2 - 字符串2
 * 返回值: 最長公共前綴的指針
 */
char* commonPrefix(char* str1, char* str2) {
    int length1 = strlen(str1);
    int length2 = strlen(str2);

    int index = 0;
    // 比較兩個字符串對應位置的字符
    while (index < length1 && index < length2 && str1[index] == str2[index]) {
        index++;
    }

    // 創建新的字符串，存儲公共前綴
    char* result = (char*)malloc((index + 1) * sizeof(char));
    strncpy(result, str1, index);
    result[index] = '\0';

    return result;
}

說明
longestCommonPrefix() 函數用于找到字符串數組中的最長公共前綴。
首先判斷字符串數組是否為空或大小為0。如果是，則直接返回空字符串。獲取字符串數組的第一個字符串 firstStr，并保存它的長度
length。遍歷第一個字符串的每個字符，并與剩余字符串的對應位置的字符進行比較，找到最長公共前綴。
如果當前字符已經超過了某個字符串的長度，或者當前字符不等于其他字符串對應位置的字符，就返回前綴部分。使用malloc()
函數動態分配內存，使用strncpy() 函數復制字符串，并在末尾添加結束符 ‘\0’，然后返回前綴字符串的指針。
如果遍歷后沒有找到不相等的字符，說明第一個字符串是最長公共前綴，返回第一個字符串的拷貝，使用strdup() 函數實現。
commonPrefix() 函數用于獲取兩個字符串的最長公共前綴的公共前綴。
在循環中，比較兩個字符串對應位置的字符，找到不相等的位置，返回前綴部分。這里使用了與之前相同的邏輯和函數。 main() 函數中調用了
longestCommonPrefix() 函數，并打印結果最長公共前綴。余下的是釋放內存的代碼，避免內存泄漏。

Python3版本

def longestCommonPrefix(strs):
    # 如果字符串數組為空或長度為0，直接返回空字符串
    if not strs:
        return ""

    # 字符串數組的第一個字符串
    firstStr = strs[0]

    # 遍歷第一個字符串的每個字符
    for i in range(len(firstStr)):
        c = firstStr[i]

        # 遍歷剩余的字符串進行比較
        for j in range(1, len(strs)):
            # 如果當前字符已經超過了某個字符串的長度，或者當前字符不等于其他字符串對應位置的字符，返回前綴部分
            if i >= len(strs[j]) or strs[j][i] != c:
                return firstStr[:i]
    
    # 返回第一個字符串作為最長公共前綴
    return firstStr

# 調用函數并打印結果
#strs = ["flower", "flow", "flight"]
#result = longestCommonPrefix(strs)
#print("Longest Common Prefix:", result)

說明： longestCommonPrefix() 函數用于找到字符串數組中的最長公共前綴。
首先判斷字符串數組是否為空。如果為空，則直接返回空字符串。獲取字符串數組的第一個字符串 firstStr。
遍歷第一個字符串的每個字符，并與剩余字符串的對應位置的字符進行比較，找到最長公共前綴。
如果當前字符已經超過了某個字符串的長度，或者當前字符不等于其他字符串對應位置的字符，就返回前綴部分。返回第一個字符串作為最長公共前綴。在
main() 函數中，調用 longestCommonPrefix() 函數，并打印結果最長公共前綴。

復雜度分析

時間復雜度：O(mn)，其中 m 是字符串數組中的字符串的平均長度，n 是字符串的數量。最壞情況下，字符串數組中的每個字符串的每個字符都會被比較一次。
空間復雜度：O(1)。使用的額外空間復雜度為常數。

方式三：分治

思路

代碼實現

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串數組為空或者長度為0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        } else {
            return longestCommonPrefix(strs, 0, strs.length - 1);
        }
    }
    
    // 遞歸函數，用于求取指定范圍內字符串數組的最長公共前綴
    public String longestCommonPrefix(String[] strs, int start, int end) {
        // 如果范圍內只有一個字符串，則直接返回該字符串作為最長公共前綴
        if (start == end) {
            return strs[start];
        } else {
            // 計算范圍中間索引
            int mid = (end - start) / 2 + start;

            // 求取左半部分和右半部分的最長公共前綴
            String lcpLeft = longestCommonPrefix(strs, start, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, end);

            // 返回左半部分和右半部分的最長公共前綴的公共前綴
            return commonPrefix(lcpLeft, lcpRight);
        }
    }
    
    // 求取兩個字符串的最長公共前綴的公共前綴
    public String commonPrefix(String lcpLeft, String lcpRight) {
        // 獲取最小長度
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());

        // 對比兩個字符串的字符，找到不相等的位置，返回前綴部分
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }

        // 返回最小長度范圍內的字符串，即最長公共前綴
        return lcpLeft.substring(0, minLength);
    }
}

說明：
longestCommonPrefix() 方法是遞歸函數，用于求取指定范圍內字符串數組 strs 的最長公共前綴。
如果范圍內只有一個字符串，則直接返回該字符串作為最長公共前綴。否則，計算范圍中間索引 mid。調用遞歸函數
longestCommonPrefix() 分別求取左半部分和右半部分的最長公共前綴：lcpLeft 和 lcpRight。
返回左半部分和右半部分的最長公共前綴的公共前綴，即調用 commonPrefix() 函數。 commonPrefix()
方法用于求取兩個字符串 lcpLeft 和 lcpRight 的最長公共前綴的公共前綴。獲取兩個字符串的長度的最小值作為最小長度minLength。逐個字符比較兩個字符串的對應位置的字符，找到不相等的位置，返回當前位置前的子串作為最長公共前綴的公共前綴。
如果沒有找到不相等的位置，返回最小長度范圍內的字符串，即最長公共前綴。

C語言版本

#include <stdio.h>
#include <string.h>

// 函數聲明
char* longestCommonPrefix(char** strs, int strsSize);

/*
 * 獲取兩個字符串的最長公共前綴
 * 參數: str1 - 字符串1, str2 - 字符串2
 * 返回值: 最長公共前綴的指針
 */
char* commonPrefix(char* str1, char* str2);
/*
 * 獲取字符串數組中的最長公共前綴
 * 參數: strs - 字符串數組, strsSize - 字符串數組的長度
 * 返回值: 最長公共前綴的指針
 */
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串數組為空或者長度為0，直接返回空字符串
    if (strs == NULL || strsSize == 0) {
        return "";
    }

    // 將第一個字符串作為初始的最長公共前綴
    char* prefix = strs[0];

    // 遍歷剩余的字符串
    for (int i = 1; i < strsSize; i++) {
        // 更新最長公共前綴為當前遍歷的字符串與最長公共前綴的公共前綴
        prefix = commonPrefix(prefix, strs[i]);

        // 如果最長公共前綴為空，說明不存在公共前綴，直接跳出循環
        if (strlen(prefix) == 0) {
            break;
        }
    }

    return prefix;
}

/*
 * 獲取兩個字符串的最長公共前綴的公共前綴
 * 參數: str1 - 字符串1, str2 - 字符串2
 * 返回值: 最長公共前綴的指針
 */
char* commonPrefix(char* str1, char* str2) {
    int length1 = strlen(str1);
    int length2 = strlen(str2);

    int index = 0;
    while (index < length1 && index < length2 && str1[index] == str2[index]) {
        index++;
    }

    // 創建新的字符串，存儲公共前綴
    char* result = (char*)malloc((index + 1) * sizeof(char));
    strncpy(result, str1, index);
    result[index] = '\0';  // 末尾添加結束符

    return result;
}

說明：
longestCommonPrefix()函數用于找到字符串數組中的最長公共前綴。
在函數中，首先判斷字符串數組是否為空或長度為0。如果是，則直接返回空字符串。將字符串數組的第一個字符串作為初始的最長公共前綴prefix。
使用一個循環遍歷剩余的字符串，分別與當前最長公共前綴進行比較，更新最長公共前綴。如果最長公共前綴為空字符串，說明不存在公共前綴，跳出循環。
返回最長公共前綴prefix的指針。 commonPrefix()函數用于找到兩個字符串的最長公共前綴的公共前綴。
在函數中，通過計算兩個字符串的長度，初始化索引index為0。
使用一個循環比較兩個字符串的對應位置字符，直到遇到不相等的字符或其中一個字符串的結尾。
創建一個新的字符數組result，用于存儲公共前綴部分。使用strncpy()函數將公共前綴部分復制到result中。
在result末尾添加結束符\0。返回公共前綴result的指針。
請注意，使用malloc()動態分配了內存空間來存儲結果字符串，因此在使用完畢后，記得使用free()函數釋放它。

Python3版本

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 定義遞歸函數，用于求取字符串數組中指定范圍內的最長公共前綴
        def lcp(start, end):
            # 如果范圍中只有一個字符串，則直接返回該字符串作為最長公共前綴
            if start == end:
                return strs[start]

            # 分治法，將范圍劃分為兩部分，分別求取左右兩部分的最長公共前綴
            mid = (start + end) // 2
            lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)

            # 找到左右兩部分最長公共前綴的最小長度
            minLength = min(len(lcpLeft), len(lcpRight))

            # 在最小長度范圍內逐個字符比較
            for i in range(minLength):
                if lcpLeft[i] != lcpRight[i]:
                    # 遇到第一個不相等的字符，返回前綴部分
                    return lcpLeft[:i]

            # 返回最小長度范圍內的最長公共前綴
            return lcpLeft[:minLength]

        # 如果字符串數組為空，則返回空字符串
        return "" if not strs else lcp(0, len(strs) - 1)

說明：
使用分治法，將指定范圍劃分為左右兩部分，分別求取它們的最長公共前綴。計算中間索引 mid。調用 lcp()
函數求取左半部分的最長公共前綴 lcpLeft。調用 lcp() 函數求取右半部分的最長公共前綴 lcpRight。
找到左右兩部分最長公共前綴的最小長度。在最小長度范圍內逐個字符比較左右兩部分的對應位置字符。
如果遇到第一個不相等的字符，返回當前位置前的子串作為最長公共前綴。返回最小長度范圍內的最長公共前綴。如果字符串數組為空，則返回空字符串。
否則，調用 lcp() 函數，傳入起始索引0和結束索引 len(strs) - 1，求取整個字符串數組的最長公共前綴。
longestCommonPrefix() 方法是主函數，用于啟動遞歸過程并處理邊界情況。lcp() 函數是一個內部遞歸函數，用于求取字符串數組中指定范圍內的最長公共前綴

復雜度分析

時間復雜度：O(mn)，其中 m 是字符串數組中的字符串的平均長度，n 是字符串的數量。時間復雜度的遞推式是 T(n)=2?T(2n )+O(m)，通過計算可得 T(n)=O(mn)。
空間復雜度：O(mlogn)，其中 m 是字符串數組中的字符串的平均長度，n 是字符串的數量。空間復雜度主要取決于遞歸調用的層數，層數最大為 logn，每層需要 m 的空間存儲返回結果。

方式四：二分查找

思路

顯然，最長公共前綴的長度不會超過字符串數組中的最短字符串的長度。用 minLength 表示字符串數組中的最短字符串的長度，則可以在 [0,minLength] 的范圍內通過二分查找得到最長公共前綴的長度。每次取查找范圍的中間值 mid，判斷每個字符串的長度為 mid 的前綴是否相同，如果相同則最長公共前綴的長度一定大于或等于 mid，如果不相同則最長公共前綴的長度一定小于 mid，通過上述方式將查找范圍縮小一半，直到得到最長公共前綴的長度。

代碼實現

Java版本

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果字符串數組為空或長度為0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        // 獲取字符串數組中最短字符串的長度
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        
        // 使用二分查找的思路來查找最長公共前綴
        int low = 0, high = minLength;
        while (low < high) {
            // 取中間位置
            int mid = (high - low + 1) / 2 + low;
            
            // 判斷中間位置的前綴是否是公共前綴
            if (isCommonPrefix(strs, mid)) {
                // 如果是，更新 low，繼續查找右半部分
                low = mid;
            } else {
                // 如果不是，更新 high，繼續查找左半部分
                high = mid - 1;
            }
        }
        
        // 返回最長公共前綴
        return strs[0].substring(0, low);
    }
    
    // 判斷指定長度前綴是否是字符串數組的公共前綴
    public boolean isCommonPrefix(String[] strs, int length) {
        // 獲取第一個字符串的指定長度前綴
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        
        // 遍歷剩余的字符串，逐個比較前綴字符
        for (int i = 1; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        
        // 返回是否是公共前綴的結果
        return true;
    }
}

說明：
longestCommonPrefix() 方法用于求取字符串數組 strs 中的最長公共前綴。
首先判斷字符串數組是否為空或長度為0，如果是，則直接返回空字符串。獲取字符串數組中最短字符串的長度 minLength。
使用二分查找的思路來查找最長公共前綴。維持一個區間 [low, high]，初始為 [0, minLength]。
在每一次循環中，取區間的中間位置 mid。判斷以mid長度作為前綴是否是字符串數組的公共前綴，通過調用 isCommonPrefix()
方法實現。如果是公共前綴，則更新 low = mid，繼續查找右半部分。如果不是公共前綴，則更新 high = mid -
1，繼續查找左半部分。當 low >= high 時，二分查找結束，得到最長公共前綴的長度。返回最長公共前綴，使用
strs[0].substring(0, low) 來截取對應長度的前綴。 isCommonPrefix()
方法用于判斷指定長度的前綴是否是字符串數組 strs 的公共前綴。獲取第一個字符串的指定長度前綴 str0。
遍歷剩余的字符串，逐個比較前綴中的字符。如果存在不相等的字符，說明不是公共前綴，返回 false。
如果所有字符串的前綴字符都相等，說明是公共前綴，返回 true。

C語言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 函數聲明
char* longestCommonPrefix(char** strs, int strsSize);
int isCommonPrefix(char** strs, int strsSize, int len);

/**
int main() {
    // 測試數據
    char* strs[] = {"flower", "flow", "flight"};
    int strsSize = 3;

    // 調用函數并打印結果
    char* result = longestCommonPrefix(strs, strsSize);
    printf("Longest Common Prefix: %s\n", result);

    return 0;
}
**/
/*
 * 獲取字符串數組中的最長公共前綴
 * 參數: strs - 字符串數組, strsSize - 字符串數組的長度
 * 返回值: 最長公共前綴的指針
 */
char* longestCommonPrefix(char** strs, int strsSize) {
    // 如果字符串數組為空或長度為0，直接返回空字符串
    if (strs == NULL || strsSize == 0) {
        return "";
    }

    // 找出最短字符串的長度
    int minLength = INT_MAX;
    for (int i = 0; i < strsSize; i++) {
        int len = strlen(strs[i]);
        if (len < minLength) {
            minLength = len;
        }
    }

    // 使用二分法查找最長公共前綴
    int low = 1;
    int high = minLength;
    int mid = 0;
    while (low <= high) {
        mid = (low + high) / 2;
        if (isCommonPrefix(strs, strsSize, mid)) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    // 根據最長公共前綴的長度，創建并返回結果字符串
    char* result = (char*)malloc((mid + 1) * sizeof(char));
    strncpy(result, strs[0], mid);
    result[mid] = '\0';

    return result;
}

/*
 * 判斷指定長度前綴是否是字符串數組的公共前綴
 * 參數: strs - 字符串數組, strsSize - 字符串數組的長度, len - 前綴長度
 * 返回值: 是否是公共前綴的整數值，1為是，0為否
 */
int isCommonPrefix(char** strs, int strsSize, int len) {
    for (int i = 0; i < len; i++) {
        char ch = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != ch) {
                return 0;
            }
        }
    }
    return 1;
}

說明：
longestCommonPrefix()函數用于找到字符串數組中的最長公共前綴。
在函數中，首先判斷字符串數組是否為空或長度為0。如果是，則直接返回空字符串。找出字符串數組中最短字符串的長度minLength。
使用二分法來查找最長公共前綴。初始化low為1，high為最短字符串的長度minLength。循環遍歷，直到找到最長公共前綴的長度。
設置mid為low和high的中間值。如果前綴長度為mid的前綴是字符串數組的公共前綴，則在[mid+1, high]范圍繼續查找。
如果前綴長度為mid的前綴不是字符串數組的公共前綴，則在[low, mid-1]范圍繼續查找。
根據最長公共前綴的長度mid，動態分配內存創建結果字符串result。
使用strncpy()函數將字符串數組的第一個字符串的前mid個字符復制到結果字符串中。在結果字符串的末尾添加結束符’\0’。
返回結果字符串的指針。請注意，在使用完結果字符串后，不要忘記使用free()函數釋放分配的內存。

Python3版本

def longestCommonPrefix(strs):
    # 如果字符串數組為空或長度為0，直接返回空字符串
    if not strs:
        return ""

    # 找出最短字符串的長度
    minLength = min(len(s) for s in strs)

    # 使用二分法查找最長公共前綴
    low = 1
    high = minLength
    while low <= high:
        mid = (low + high) // 2
        if isCommonPrefix(strs, mid):
            low = mid + 1
        else:
            high = mid - 1

    # 根據最長公共前綴的長度，返回結果字符串
    return strs[0][:low]

def isCommonPrefix(strs, length):
    for i in range(length):
        ch = strs[0][i]
        for j in range(1, len(strs)):
            if strs[j][i] != ch:
                return False
    return True

# 調用函數并打印結果
#strs = ["flower", "flow", "flight"]
#result = longestCommonPrefix(strs)
#print("Longest Common Prefix:", result)

說明：
longestCommonPrefix() 函數用于找到字符串數組中的最長公共前綴。
首先判斷字符串數組是否為空。如果為空，則直接返回空字符串。找出字符串數組中最短字符串的長度 minLength，使用 min()函數和生成器表達式來實現。使用二分法來查找最長公共前綴。初始化 low 為 1，high 為最短字符串的長度 minLength。
循環遍歷，直到找到最長公共前綴的長度。設置 mid 為 low 和 high 的中間值。如果前綴長度為 mid
的前綴是字符串數組的公共前綴，則在 [mid+1, high] 范圍繼續查找。如果前綴長度為 mid 的前綴不是字符串數組的公共前綴，則在[low, mid-1] 范圍繼續查找。根據最長公共前綴的長度 low，返回結果字符串，使用切片操作實現。
isCommonPrefix() 函數用于判斷指定長度的前綴是否是字符串數組的公共前綴。
使用嵌套循環遍歷前綴的每個字符，逐個比較所有字符串的對應位置字符。如果存在不相等的字符，說明不是公共前綴，返回 False。
如果所有字符串的前綴字符都相等，說明是公共前綴，返回 True。調用函數并打印結果，使用示例字符串數組。

復雜度分析

時間復雜度：O(mnlogm)，其中 m 是字符串數組中的字符串的最小長度，n 是字符串的數量。二分查找的迭代執行次數是 O(logm)，每次迭代最多需要比較 mn 個字符，因此總時間復雜度是 O(mnlogm)。
空間復雜度：O(1)。使用的額外空間復雜度為常數。

總結

解法	思路	優點	缺點	時間復雜度	空間復雜度
橫向掃描	從第一個字符串作為初始公共前綴，逐個與后續字符串比較，更新公共前綴	簡單直觀，易于理解和實現	需要進行多次字符比較，時間復雜度較高	O(m*n)	O(1)
縱向掃描	逐個字符縱向比較字符串，直到遇到不匹配的字符	高效，提前結束不匹配的情況，減少不必要的比較	需要對全部字符串進行縱向比較，容易漏掉一些情況	O(m*n)	O(1)
分治法	將字符串數組分成子問題，分別求解左右兩組的公共前綴，最后合并得到最長公共前綴	減小了比較的次數，更加高效	在字符串數組較大時，遞歸和合并操作可能導致額外的開銷	O(mnlogk)	O(m*logk)
二分法	將字符串數組二分，求左右兩組的公共前綴，最后求兩者的公共前綴	大大減少了比較的次數，更加高效	需要對字符串數組進行分割和合并，增加了分配內存的開銷	O(mnlogm)	O(m)

其中，m 為字符串的平均長度，n 為字符串數組的長度，k 為字符串數組中的字符串字符最大長度。需要注意的是，在實際應用中，具體優化技巧和實現方法可能會對復雜度產生影響。因此，上述復雜度分析僅提供了一般情況下的大致估計。

相似題目

題目	描述	難度	LeetCode鏈接
最長回文子串	尋找給定字符串中的最長回文子串	中等	LeetCode 5
最長有效括號	尋找給定字符串中的最長有效括號序列	困難	LeetCode 32
最長連續遞增序列	尋找給定數組中的最長連續遞增子序列	簡單	LeetCode 674
最長連續序列	尋找給定數組中的最長連續序列	困難	LeetCode 128

posted on 2024-03-31 11:18 vow007 閱讀(432) 評論(0) 收藏舉報來源

刷新頁面返回頂部