Valid Parenthesis Problem Index Out of Range (Go)

huangapple go评论79阅读模式
英文:

Valid Parenthesis Problem Index Out of Range (Go)

问题

这个问题的原因是数组越界错误。在代码中,当检测到字符为")"时,会尝试访问数组arr的最后一个元素arr[len(s) - 1]。然而,len(s)返回的是字符串s的长度,而不是数组arr的长度。因此,当s的长度为1时,访问arr[len(s) - 1]就会导致数组越界错误。

英文:

I was converting code for a problem I previously solved in Python into Go and ran into a runtime error: index out of range [1] with length 1 on this line

 if string(s[i]) == ")" && arr[len(s) - 1] == "("{

Here is the code in entirety.

func isValid(s string) bool {
    arr := make([]string, 0)
    if len(s) < 2 {
        return false 
    }

    for i := 0; i < len(s); i++ {

        if string(s[i]) == "(" || string(s[i]) == "[" || string(s[i]) == "{" {
            arr = append(arr, string(s[i]))
        } else if string(s[i]) == ")" || string(s[i]) == "]" || string(s[i]) == "}" {
            if len(arr) >= 1 { 
                if string(s[i]) == ")" && arr[len(s) - 1] == "("{ 
                    arr = arr[:len(arr) -1]
                } else if string(s[i]) == "]" && arr[len(s) - 1] == "[" {
                    arr = arr[:len(arr) -1]
                } else if string(s[i]) == "}" && arr[len(s) - 1] == "{" {
                    arr = arr[:len(arr) -1]
                }  else {
                    return false
                }
            }else {
                return false
            }
    }
    }
    if reflect.DeepEqual(arr, []string{""}) {
        return true
    } else  {
        return false
    }
    
}

What is the cause of the issue?

答案1

得分: 2

你使用了len(s)-1来找到arr的最后一个索引,但应该是len(arr)-1

以下是修复了一些其他错误并避免不必要的字符转换的代码的工作版本。https://go.dev/play/p/sazf2RguoIr

package main

import "fmt"

func isValid(s string) bool {
    var arr []rune
    for _, c := range s {
        if c == '(' || c == '[' || c == '{' {
            arr = append(arr, c)
        } else if c == ')' || c == ']' || c == '}' {
            if len(arr) == 0 {
                return false
            }
            var last rune
            arr, last = arr[:len(arr)-1], arr[len(arr)-1]
            if c == ')' && last != '(' || c == ']' && last != '[' || c == '}' && last != '{' {
                return false
            }
        }
    }
    return len(arr) == 0
}

func main() {
    cases := []string{
        "()[({}())]",
        "(]",
        "((())",
        "{{{}}}",
        "{{{[][][]}}}",
    }
    for _, c := range cases {
        fmt.Println(c, isValid(c))
    }
}
英文:

You've used len(s)-1 to find the last index of arr, but it should be len(arr)-1.

Here's a working version of your code, that fixes some additional bugs, and avoids needless conversion to string for single characters. https://go.dev/play/p/sazf2RguoIr

package main

import "fmt"

func isValid(s string) bool {
	var arr []rune
	for _, c := range s {
		if c == '(' || c == '[' || c == '{' {
			arr = append(arr, c)
		} else if c == ')' || c == ']' || c == '}' {
			if len(arr) == 0 {
				return false
			}
			var last rune
			arr, last = arr[:len(arr)-1], arr[len(arr)-1]
			if c == ')' && last != '(' || c == ']' && last != '[' || c == '}' && last != '{' {
				return false
			}
		}
	}
	return len(arr) == 0
}

func main() {
	cases := []string{
		"()[({}())]",
		"(]",
		"((())",
		"{{{}}}",
		"{{{[][][]}}}",
	}
	for _, c := range cases {
		fmt.Println(c, isValid(c))
	}
}

huangapple
  • 本文由 发表于 2022年2月9日 23:41:40
  • 转载请务必保留本文链接:https://go.coder-hub.com/71052550.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定