题目

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:

  1. Input: ["flower","flow","flight"]
  2. Output: "fl"

Example 2:

  1. Input: ["dog","racecar","car"]
  2. Output: ""
  3. Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

题意

找到给定字符串组的公共前缀。

思路

以第一个字符串中的字符为基准，再去比对其余字符串中对应位置处的字符。

代码实现

Java

  1. class Solution {
  2.     public String longestCommonPrefix(String[] strs) {
  3.         if (strs == null || strs.length == 0) {
  4.             return "";
  5.         }
  6.         String ans = "";
  7.         for (int i = 0; i < strs[0].length(); i++) {
  8.             char c = strs[0].charAt(i);
  9.             for (int j = 1; j < strs.length; j++) {
  10.                 if (i == strs[j].length() || strs[j].charAt(i) != c) {
  11.                     return ans;
  12.                 }
  13.             }
  14.             ans += c;
  15.         }
  16.         return ans;
  17.     }
  18. }

JavaScript

  1. /**
  2.  * @param {string[]} strs
  3.  * @return {string}
  4.  */
  5. var longestCommonPrefix = function (strs) {
  6.   if (strs.length === 0) {
  7.     return ''
  8.   }
  10.   let prefix = ''
  12.   for (let i = 0; i < strs[0].length; i++) {
  13.     let c = strs[0][i]
  14.     for (let j = 1; j < strs.length; j++) {
  15.       if (i === strs[j].length || strs[j][i] !== c) {
  16.         return prefix
  17.       }
  18.     }
  19.     prefix += c
  20.   }
  22.   return prefix
  23. }