Valid Parenthesis Problem Index Out of Range (Go)

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

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

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

Here is the code in entirety.

  1. func isValid(s string) bool {
  2.     arr := make([]string, 0)
  3.     if len(s) < 2 {
  4.         return false 
  5.     }
  7.     for i := 0; i < len(s); i++ {
  9.         if string(s[i]) == "(" || string(s[i]) == "[" || string(s[i]) == "{" {
  10.             arr = append(arr, string(s[i]))
  11.         } else if string(s[i]) == ")" || string(s[i]) == "]" || string(s[i]) == "}" {
  12.             if len(arr) >= 1 { 
  13.                 if string(s[i]) == ")" && arr[len(s) - 1] == "("{ 
  14.                     arr = arr[:len(arr) -1]
  15.                 } else if string(s[i]) == "]" && arr[len(s) - 1] == "[" {
  16.                     arr = arr[:len(arr) -1]
  17.                 } else if string(s[i]) == "}" && arr[len(s) - 1] == "{" {
  18.                     arr = arr[:len(arr) -1]
  19.                 }  else {
  20.                     return false
  21.                 }
  22.             }else {
  23.                 return false
  24.             }
  25.     }
  26.     }
  27.     if reflect.DeepEqual(arr, []string{""}) {
  28.         return true
  29.     } else  {
  30.         return false
  31.     }
  32.     
  33. }

What is the cause of the issue?

答案1

得分: 2

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

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

  1. package main
  3. import "fmt"
  5. func isValid(s string) bool {
  6.     var arr []rune
  7.     for _, c := range s {
  8.         if c == '(' || c == '[' || c == '{' {
  9.             arr = append(arr, c)
  10.         } else if c == ')' || c == ']' || c == '}' {
  11.             if len(arr) == 0 {
  12.                 return false
  13.             }
  14.             var last rune
  15.             arr, last = arr[:len(arr)-1], arr[len(arr)-1]
  16.             if c == ')' && last != '(' || c == ']' && last != '[' || c == '}' && last != '{' {
  17.                 return false
  18.             }
  19.         }
  20.     }
  21.     return len(arr) == 0
  22. }
  24. func main() {
  25.     cases := []string{
  26.         "()[({}())]",
  27.         "(]",
  28.         "((())",
  29.         "{{{}}}",
  30.         "{{{[][][]}}}",
  31.     }
  32.     for _, c := range cases {
  33.         fmt.Println(c, isValid(c))
  34.     }
  35. }
英文:

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

  1. package main
  3. import "fmt"
  5. func isValid(s string) bool {
  6. 	var arr []rune
  7. 	for _, c := range s {
  8. 		if c == '(' || c == '[' || c == '{' {
  9. 			arr = append(arr, c)
  10. 		} else if c == ')' || c == ']' || c == '}' {
  11. 			if len(arr) == 0 {
  12. 				return false
  13. 			}
  14. 			var last rune
  15. 			arr, last = arr[:len(arr)-1], arr[len(arr)-1]
  16. 			if c == ')' && last != '(' || c == ']' && last != '[' || c == '}' && last != '{' {
  17. 				return false
  18. 			}
  19. 		}
  20. 	}
  21. 	return len(arr) == 0
  22. }
  24. func main() {
  25. 	cases := []string{
  26. 		"()[({}())]",
  27. 		"(]",
  28. 		"((())",
  29. 		"{{{}}}",
  30. 		"{{{[][][]}}}",
  31. 	}
  32. 	for _, c := range cases {
  33. 		fmt.Println(c, isValid(c))
  34. 	}
  35. }

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

发表评论

匿名网友

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

确定