14. Longest public prefix

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

Return empty string “” if no common prefix exists

Input: STRS = ["flower","flow","flight"] Output: "fl" Input: STRS = ["dog","racecar","car"] Output: "" Explanation: The input does not have a common prefix.Copy the code

Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The first idea is to take the shortest substring Si and then decrement bit by bit to determine whether the substring is a common prefix.

Knowledge related to Go includes:

1. Basic operation of Go array:

How to traverse a number array to find the shortest substring? There are three ways to do for: I’ll call it normal for, replace for while, for-range

(1) Normal for

a := []int{0.1.2.3.4}
for i := 0; i < len(a); i++ {
    fmt.Println(a[i])
}
Copy the code

(2) Replace for while:

numLessThan3 := 0
for numLessThan3 < 3 {
    numLessThan3++
    fmt.Println(numLessThan3)
}
fmt.Println("over...")
Copy the code

(3) for-range: traverses arrays, slices, maps, etc. When a certain value is not needed, it can be replaced by “_”. Understand a new type of channel, temporarily omitted table.

For arrays: the first parameter represents the index, and the second parameter represents the value.

/ / array
a := []int{034.122.222.3222.2234}
for i, v := range a { 
    fmt.Println(i)
    fmt.Println(v)
}
for _, v := range a { 
    //fmt.Println(i)
    fmt.Println(v)
}
Copy the code

For map: the first parameter indicates the key, and the second parameter indicates the value.

// map
a := make(map[string]string.2)
a["k1"] = "value1"
a["k2"] = "value2"
for k, v := range a {
    fmt.Println(k)
    fmt.Println(v)
}
Copy the code

2. Section:

How to slice from a string as a new string: Slicing, similar to slicing in Python but slightly different, Go does not support reciprocal slicing.

a := []int{0.1.2.3.4}
fmt.Println(a)  	// [0 1 2 3 4]
fmt.Println(a[0:2]) / / [0, 1]
fmt.Println(a[:2])  / / [0, 1]
fmt.Println(a[2:4]) / / [2, 3]
// fmt.Println(a[2:-1]) invalid slice index -1 (index must be non-negative)
fmt.Println(a[2:)/ / [2, 3, 4]

// Reverse slice
// fmt.Println(a[-2:]) invalid slice index -2 (index must be non-negative)
Copy the code

3. Judge prefixes:

How to determine if a string is a prefix of another string:

We can loop to determine whether each character of the string is the same or strings.hasprefix (s, prefix String).

Back to the problem, the implementation code is as follows:

package main

import (
	"fmt"
	"strings"
)

func main(a) {
	strs := []string{"a"."a23"."abc"}
	fmt.Println(longestCommonPrefix(strs))
}

func longestCommonPrefix(strs []string) string {
    // I forgot the boundary conditions on my first run
    if len(strs) == 0 {
		return ""
	}

	// Find the shortest substring
	shortestStr, shortestLength := strs[0].len(strs[0])
	for _, value := range strs {
		if len(value) < shortestLength {
			shortestLength = len(value)
			shortestStr = value
		}
	}


	for i := shortestLength; i > 0; i-- {
		if isCommonPrefix(shortestStr[:i], strs) {
			return shortestStr[:i]
		}
	}

	return ""
}


func isCommonPrefix(prefix string, strs []string) bool {
	// Determine bitwise, or use the strings.HasPrefix function
	for _, value := range strs {
		if! strings.HasPrefix(value, prefix) {return false}}return true
}
Copy the code

One final question: what does ftt.println (034) print?

Hint: numbers starting with 0- are considered base 8.