How to solve the problem of longest Common prefix in leetcode

This article mainly introduces how to solve the problem of the longest common prefix in leetcode. It is very detailed and has a certain reference value. Friends who are interested must read it!

Topic link

Https://leetcode-cn.com/problems/longest-common-prefix/

Topic description

Write a function to find the longest common prefix in a string array.

If no common prefix exists, an empty string "" is returned.

Example 1:

Input: ["flower", "flow", "flight"] output: "fl"

Example 2:

Input: ["dog", "racecar", "car"] output: "" explanation: input does not have a common prefix.

Description:

All inputs contain only the lowercase letter amurz.

The idea of solving the problem

Tags: strin

When the length of the string array is 0, the common prefix is empty and returns directly

Initialize the value of the longest common prefix ans to the first string

Traverse the following string, compare it with ans in turn, find out the common prefix in pairs, and the final result is the longest common prefix.

If an empty ans occurs during the lookup, there is no direct return of the common prefix

Time complexity: O (s), s is the sum of the length of all strings

Code

Java version

Class Solution {public String longestCommonPrefix (String [] strs) {if (strs.length = = 0) return ""; String ans = strs [0]; for (int I = 1