0
if (i - word.size() >= 0 && dp[i - word.size()] && s.substr(i - word.size(), word.size()) == word)
    dp[i] = true;

i - word.size() >= 0 is the condition that I was using to prevent an out-of-bound indexing. The expectation was that if the condition was not satisfied, the equation would short circuit and the reference dp[i - word.size()] would not be happen.

But the reference happened regardless of the first condition. Only when I changed the code to the following, it started to short circuit.

int lookback = i - word.size();
if (lookback >= 0 && dp[lookback] && s.substr(i - word.size(), word.size()) == word)
    dp[i] = true;

Why does the second code short circuit while the first one doesn't? I've read that if the logical operators && and || are overloaded, short circuiting doesn't happen, but that doesn't seem to be the case here and I can't figure out why it's not happening.

Here's the full code for context

bool wordBreakFaulty(string s, vector<string>& wordDict) {
    int n = s.size() + 1;
    vector<bool> dp(n, false);
    dp[0] = true;
    for (int i = 1; i < dp.size(); ++i) {
        for (auto& word : wordDict) {
            if (i - word.size() >= 0 && dp[i - word.size()] && s.substr(i - word.size(), word.size()) == word)
                dp[i] = true;
        }
    }

    return dp.back();
}
Jeremy Friesner
  • 70,199
  • 15
  • 131
  • 234
  • Check what type `word.size()` returns. Then read about [arithmetic conversions](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Conversions) – Nate Eldredge Aug 09 '22 at 01:58
  • 1
    always enable compiler warnings. You'll get a cast warning in `int lookback = i - word.size();` or an "always true" warning in `i - word.size() >= 0` – phuclv Aug 09 '22 at 01:59
  • Thank you!!!! I really should have thought of it. – cupbear Aug 09 '22 at 02:03
  • 1
    @phuclv — you’ll get a **conversion** warning. There are no casts in that code. – Pete Becker Aug 09 '22 at 02:09

0 Answers0