Longest string of subroutines

Given a string s, find the longest substring in s.

Input: s = “babad” Output: “bab” Explanation: “ABA” is also the answer to the question.

Input: s = “CBBD” Output: “bb”

Input: s = “a” Output: “a”

Input: s = “AC”

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.

This solution involves the Go language array, and the knowledge of strings includes:

1. How to define multidimensional arrays in Go:

var s = [][]int{{1.2.3}, {4.5.6}}
var s1 = [2] [3]int{{1.2.3}, {4.5.6}}
var s2 = [3] [3]int{{1.2.3}, {4.5.6}}
println(len(s)) / / 2
println(len(s1)) / / 2
println(len(s2)) / / 3
Copy the code

2. How to define a dynamic two-dimensional array in Go:

	n, m := 2.3
	arr := make([] []int, n)
	for i := 0; i < len(arr); i++ {
		arr[i] = make([]int, m)
	}
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr[i]); j++ {
			println(arr[i][j])
		}
	}
Copy the code

3. Add elements to the array using append

I just learned to use it in GoappendAdd elements to an arrayvar a []int
a = append(a, 1)
var arr [][]int
row1 := []int{1.2.3}
row2 := []int{4.5.6}
arr = append(arr, row1)
arr = append(arr, row2)
Copy the code

4. How to convert string and array in Go:

// If there are no Chinese characters, use byte
en := "124"
enArray := []byte(en)
// Use rune when there are Chinese characters or special characters
ch := "Hello" ABC ""
chArray := []rune(ch)
chByteArray := []byte(ch)
println(len(enArray)) / / 3
println(len(chArray)) / / 5
println(len(chByteArray)) // 9, a Chinese character takes up 3 bytes
Copy the code

This paper uses Go language to implement dynamic programming algorithm.

In the process of retrieving data, I saw a very interesting understanding of dynamic programming:

Dynamic Programming is just a fancy way to say ‘remember stuff to save time later’

Define the state characteristics of the optimal solution of dynamic programming: is_palindrome[I] [j] is equal to true or false, indicating whether the i-th to j-letter string of string S is a palindrome string.

Dynamic programming state transition equation/recursive formula: Transitions from short strings to long strings

Dynamic programming boundary conditions/initialization: when I =j, is_Palindrome [I] [j]= true, is_palindrome[I] [I + 1] = S [I]= = S [I + 1].

The dynamic programming code is implemented as follows:

func longestPalindrome(s string) string {
	runeS := []rune(s)
	length := len(runeS)
	/** * dp := make([length][length]bool) * /
	dp := make([] []bool.len(runeS))
	for i := 0; i < len(runeS); i++ {
		dp[i] = make([]bool.len(runeS))
	}
	targetLeft := 0
	targetLength := 1


	for right := 0; right < length; right++ {
		Left ==right = true; left==right = true
		for left := 0; left <= right; left++ {
			// println("left = ", left, ", runeS[left] = " + string(runeS[left]))
			// println("right = ", right, ", runeS[right] = " + string(runeS[right]))
			if left == right {
				// println("left === right")
				dp[left][right] = true
			} else if right -left == 1 {
				// println("right - left = 1")
				dp[left][right] = (runeS[left] == runeS[right])
			} else {
				// println("test..." )
				dp[left][right] = dp[left+1][right- 1] && runeS[left] == runeS[right]
			}

			if dp[left][right] && (right - left + 1) > targetLength {
				targetLength = right - left + 1
				targetLeft = left
				
				// println("s[left][right] = " + string(runeS[targetLeft:targetLeft+targetLength-1]))}}}return string(runeS[targetLeft:targetLeft+targetLength])
}
Copy the code

The lesson: print

The first time I did not screen println, it timed out, so I will try my best to remove print in the production environment!!

Manacher algorithm code parsing: make a long time algorithm, or the code is easier to understand:

/**
* Manacher
*/
func longestPalindrome(s string) string {
	start, end := 0.- 1
	t := "#"
	for i := 0; i < len(s); i++ {
		t += string(s[i]) + "#"
	}
	t += "#"
	s = t
	println(s)
	// Store the maximum arm length for each position
	arm_len := []int{}
	// Right represents the rightmost edge of the search
	right, j := - 1.- 1
	for i := 0; i < len(s); i++ {
		// For each I point
		var cur_arm_len int
		if right >= i { // point I is to the left of point right
			// i_sym is the point of symmetry between I and j
			i_sym := j*2-i
			// The shortest arm length of point I
			min_arm_len := min(arm_len[i_sym], right-i)
			// Search from the shortest arm length
			cur_arm_len = expand(s, i-min_arm_len, 	i+min_arm_len)
		} else { // point I is to the right of point RIGHT
			cur_arm_len = expand(s, i, i)
		}
		// Record the maximum arm length of point I
		arm_len = append(arm_len, cur_arm_len)
		if i + cur_arm_len > right {
            // Update the location of center j
            j = i
			// Update the location of right
			right = i +  cur_arm_len
		}
		if cur_arm_len*2+1 > end - start {
			// The maximum arm length is updated
			start = i - cur_arm_len
			end = i + cur_arm_len
		}
	}
	ans := ""
	for i := start; i <= end; i++ {
		ifs[i] ! =The '#' {
			ans += string(s[i])
		}
	}
	return ans
}

func expand(s string, left, right int) int {
	for; left>=0&&right<len(s)&&s[left]==s[right]; left, right = left- 1, right + 1{}
	// We want the arm length, so we need to divide by 2
	return (right - left 2 -) / 2
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
Copy the code

Go language power buckle brush series of articles | Go theme month

  1. Go language power buckle brush – the sum of two numbers | Go theme month

  2. Go language power buckle brush – add two numbers | Go theme months

  3. Go language power button brush title – the largest string without repeating characters | Go theme month

  4. Go language power button brush questions – find the median of two positive ordinal groups | Go theme months