Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Find the common longest prefix in the string array.”

Title link: Source: LeetCode

Link: 14. Longest Public Prefix – LeetCode (leetcode-cn.com)

2

Write a function to find the longest public prefix in an array of strings.

Returns the empty string “” if no public prefix exists.

Example 1: Input: STRS = ["flower","flow","flight"] Output: flCopy the code
Example 2: Input: STRS = ["dog","cat","rabbit"] Output: "" Parsing: Input does not have a common prefixCopy the code

Second, the problem solving

1. Analysis of ideas

If they are the same, then compare the next column. If they are different, then the current column does not belong to the public prefix, so the column between the current column is the longest public prefix.

2. Code implementation

Get the length of the first string in the string array, and then iterate over it to compare with other strings.

Take characters at the same position of each string and check if they are the same.

public class Solution 
{
    public string LongestCommonPrefix(string[] strs) 
    {
        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][i];
            for (int j = 0; j < count; j++)
            {
                if(i == strs[j].Length || strs[j][i] ! = c) {return strs[0].Substring(0, i); }}}return strs[0]; }}Copy the code

3. Time complexity

Time complexity: O(Mn)

Where m is the average length of strings in the string array and n is the number of strings. In the worst case, each character of each string in the string array is compared once.

Space complexity: O(1)

The extra space complexity used is constant.

Third, summary

This problem with vertical comparison is more in line with people’s habits of thinking, this algorithm is also based on the habit of thinking algorithm.

If you want to know the longest public prefix, you must traverse all characters, so it is obviously more reasonable to use only the public prefix length * the number of strings in vertical comparison.