演算法-最長公共前綴

• 2022 年 7 月 29 日
• 筆記
• leetcode, 數組, 演算法

01、題目分析

編寫一個函數來查找字元串數組中的最長公共前綴。如果不存在公共前綴，則返回””【leetcode】

示例1

輸入: ["flower","flow","flight"]
輸出: "fl"

示例2

輸入: ["dog","racecar","car"]
輸出: ""

解釋：輸入不存在公共前綴。

02、題解分析

方法1

假定我們現在就從一個數組中尋找最長公共前綴，那麼首先，我們可以將第一個元素設置為基準元素x0。假如數組為[“flow”,”flower”,”flight”]，flow就是我們的基準元素base。然後我們只需要依次將基準元素和後面的元素進行比較（假定後面的元素依次為s1,s2,s3….），不斷更新基準元素，直到基準元素和所有元素都滿足最長公共前綴的條件，就可以得到最長公共前綴。
具體比對過程如下：
先申請一塊地址空間commonPrefix，大小是第一個字元串的大小+1，並全置為’\0’。依次將si與base逐個字母比較，當不等時候，將相等部分拷貝到commonPrefix，然後更新bese，最後就是想要的結果（一開始base=flower，flower和flow比較，然後base更新為flow，然後用這個base和s2比較，以此類推）

我們需要注意的是，在處理基準元素的過程中，如果基準元素和任一一個元素無法匹配，則說明不存在最長公共元素。最後，我們記得處理一下臨界條件。如果給定數組是空，也說明沒有最長公共元素。

方法2

先申請一塊地址空間，大小是第一個字元串的大小+1，並全置為’\0’。縱向掃描時，從前往後遍歷所有字元串的每一列，比較相同列上的字元是否相同，如果相同則繼續對下一列進行比較，如果不相同則當前列不再屬於公共前綴，當前列之前的部分為最長公共前綴。

初始狀態

結束狀態

03、題解

方法1

char* longestCommonPrefix(char** strs, int strsLen ) {
  if (strsLen == 0)
    return "";

  if (strsLen == 1)
    return *strs;

  int i, j, k;
  char* base = strs[0];

  char* commonPrefix = (char*)malloc((strlen(base) + 1) * sizeof(char));
  memset(commonPrefix, '\0', strlen(base) + 1);

  for (i = 1; i < strsLen; i++) {
    // j 指向每個字母
    for (j = 0; j < strlen(base); j++) {
      if (strs[i][j] != base[j]) {
        strncpy(commonPrefix, base, j);
          for (k = j; k < strlen(commonPrefix); k++){
            commonPrefix[k] = '\0';
          }
          base = commonPrefix;
      }
    }
  }
  return base;
}

方法2

// 方法2
char * longestCommonPrefix(char ** strs, int strsSize){
  if(strsSize == 0)
    return "";

  if(strsSize == 1)
    return *strs;
  
  //申請7個字元，最後一個存放 '\0' 
  char *commonPrefix = (char *)malloc((strlen(strs[0]) + 1) * sizeof(char)); 
  memset(commonPrefix, '\0', strlen(strs[0]) + 1);  

  int i,j;

  // i分別指向每一個字母  
  for (i = 0; i < strlen(strs[0]); i++) {
    // j 指向每一個單詞 
    char c = strs[0][i];
    for(j = 0; j < strsSize; j++) {
      if(strs[j][i] != c) {
           strncpy(commonPrefix, strs[0], i);
           return commonPrefix;
        }   
    }
  }
  return strs[0];
}

04、測試結果

  int strsLen = 3
  char* strs[strsLen] = {"flow","flower", "flight"}