Skip to main content
Code Review

Return to Answer

Fixed incorrect big-O classification
Source Link
Pieter Witvoet
Pieter Witvoet
  • 8.3k
  • 16
  • 28

Memoization

Looking into memoization is a good idea - in this case it allows you to achieve \$O(n)\$ runtime performance instead of \$O(n^2)\$\$O(2^n)\$. One way to add memoization is to create a wrapper method that takes the same arguments as Decode. This method first looks up the given arguments in a dictionary, and if they're present, it can return the memoized result. If not, it will call Decode and store its result in the dictionary before returning it.

However, I would recommend removing NumDecodings and rewriting Decode so it only takes a single string parameter. That will simplify memoization and make it a little more efficient. For example, "412123" and "512123" both have the same suffix ("12123"), but because the 'sub-calls' ("412123", 1, 1) and ("512123", 1, 1) use different arguments (and thus different memoization keys) you won't benefit from memoization across those different inputs.

Other notes

  • Instead of passing the original input string and an offset and length, consider passing 'the rest of the string' instead. Decode can then call Decode(s.Substring(1)) if the leading digit is a valid unit, and Decode(s.Substring(2)) if the leading 2 digits are a valid unit.
  • There are various things in the current code that can be simplified:
    • if (i + len - 1 >= s.Length) to if (i + len > s.Length)
    • s.Substring(i, len)[0] == '0' to s[i] == '0'
    • else if (i + len - 1 == s.Length - 1 to else if (i + len == s.Length
    • jump1 = i + len - 1 + 1 to jump1 = i + len
    • jump2 = i + len - 1 + 2 to jump2 = i + len + 1
  • Moving s.Substring(i, len)[0] == '0' to an else if branch allows you to remove the sub < 27 && sub > 0 checks below.
  • Disabling code during development is normal, but it's a good idea to clean things up from time to time.
  • I would rename Decode to something more descriptive like ValidDecodingsCount - Decode implies that it actually decodes the given input, which is not the case. jump1 and jump2 aren't very descriptive names either, but it's a bit difficult to come up with better names. Maybe rest1Combinations and rest2Combinations?

Memoization

Looking into memoization is a good idea - in this case it allows you to achieve \$O(n)\$ runtime performance instead of \$O(n^2)\$. One way to add memoization is to create a wrapper method that takes the same arguments as Decode. This method first looks up the given arguments in a dictionary, and if they're present, it can return the memoized result. If not, it will call Decode and store its result in the dictionary before returning it.

However, I would recommend removing NumDecodings and rewriting Decode so it only takes a single string parameter. That will simplify memoization and make it a little more efficient. For example, "412123" and "512123" both have the same suffix ("12123"), but because the 'sub-calls' ("412123", 1, 1) and ("512123", 1, 1) use different arguments (and thus different memoization keys) you won't benefit from memoization across those different inputs.

Other notes

  • Instead of passing the original input string and an offset and length, consider passing 'the rest of the string' instead. Decode can then call Decode(s.Substring(1)) if the leading digit is a valid unit, and Decode(s.Substring(2)) if the leading 2 digits are a valid unit.
  • There are various things in the current code that can be simplified:
    • if (i + len - 1 >= s.Length) to if (i + len > s.Length)
    • s.Substring(i, len)[0] == '0' to s[i] == '0'
    • else if (i + len - 1 == s.Length - 1 to else if (i + len == s.Length
    • jump1 = i + len - 1 + 1 to jump1 = i + len
    • jump2 = i + len - 1 + 2 to jump2 = i + len + 1
  • Moving s.Substring(i, len)[0] == '0' to an else if branch allows you to remove the sub < 27 && sub > 0 checks below.
  • Disabling code during development is normal, but it's a good idea to clean things up from time to time.
  • I would rename Decode to something more descriptive like ValidDecodingsCount - Decode implies that it actually decodes the given input, which is not the case. jump1 and jump2 aren't very descriptive names either, but it's a bit difficult to come up with better names. Maybe rest1Combinations and rest2Combinations?

Memoization

Looking into memoization is a good idea - in this case it allows you to achieve \$O(n)\$ runtime performance instead of \$O(2^n)\$. One way to add memoization is to create a wrapper method that takes the same arguments as Decode. This method first looks up the given arguments in a dictionary, and if they're present, it can return the memoized result. If not, it will call Decode and store its result in the dictionary before returning it.

However, I would recommend removing NumDecodings and rewriting Decode so it only takes a single string parameter. That will simplify memoization and make it a little more efficient. For example, "412123" and "512123" both have the same suffix ("12123"), but because the 'sub-calls' ("412123", 1, 1) and ("512123", 1, 1) use different arguments (and thus different memoization keys) you won't benefit from memoization across those different inputs.

Other notes

  • Instead of passing the original input string and an offset and length, consider passing 'the rest of the string' instead. Decode can then call Decode(s.Substring(1)) if the leading digit is a valid unit, and Decode(s.Substring(2)) if the leading 2 digits are a valid unit.
  • There are various things in the current code that can be simplified:
    • if (i + len - 1 >= s.Length) to if (i + len > s.Length)
    • s.Substring(i, len)[0] == '0' to s[i] == '0'
    • else if (i + len - 1 == s.Length - 1 to else if (i + len == s.Length
    • jump1 = i + len - 1 + 1 to jump1 = i + len
    • jump2 = i + len - 1 + 2 to jump2 = i + len + 1
  • Moving s.Substring(i, len)[0] == '0' to an else if branch allows you to remove the sub < 27 && sub > 0 checks below.
  • Disabling code during development is normal, but it's a good idea to clean things up from time to time.
  • I would rename Decode to something more descriptive like ValidDecodingsCount - Decode implies that it actually decodes the given input, which is not the case. jump1 and jump2 aren't very descriptive names either, but it's a bit difficult to come up with better names. Maybe rest1Combinations and rest2Combinations?
Source Link
Pieter Witvoet
Pieter Witvoet
  • 8.3k
  • 16
  • 28

Memoization

Looking into memoization is a good idea - in this case it allows you to achieve \$O(n)\$ runtime performance instead of \$O(n^2)\$. One way to add memoization is to create a wrapper method that takes the same arguments as Decode. This method first looks up the given arguments in a dictionary, and if they're present, it can return the memoized result. If not, it will call Decode and store its result in the dictionary before returning it.

However, I would recommend removing NumDecodings and rewriting Decode so it only takes a single string parameter. That will simplify memoization and make it a little more efficient. For example, "412123" and "512123" both have the same suffix ("12123"), but because the 'sub-calls' ("412123", 1, 1) and ("512123", 1, 1) use different arguments (and thus different memoization keys) you won't benefit from memoization across those different inputs.

Other notes

  • Instead of passing the original input string and an offset and length, consider passing 'the rest of the string' instead. Decode can then call Decode(s.Substring(1)) if the leading digit is a valid unit, and Decode(s.Substring(2)) if the leading 2 digits are a valid unit.
  • There are various things in the current code that can be simplified:
    • if (i + len - 1 >= s.Length) to if (i + len > s.Length)
    • s.Substring(i, len)[0] == '0' to s[i] == '0'
    • else if (i + len - 1 == s.Length - 1 to else if (i + len == s.Length
    • jump1 = i + len - 1 + 1 to jump1 = i + len
    • jump2 = i + len - 1 + 2 to jump2 = i + len + 1
  • Moving s.Substring(i, len)[0] == '0' to an else if branch allows you to remove the sub < 27 && sub > 0 checks below.
  • Disabling code during development is normal, but it's a good idea to clean things up from time to time.
  • I would rename Decode to something more descriptive like ValidDecodingsCount - Decode implies that it actually decodes the given input, which is not the case. jump1 and jump2 aren't very descriptive names either, but it's a bit difficult to come up with better names. Maybe rest1Combinations and rest2Combinations?