Return to Answer

• For each index offset in the input string from 0 to s.size() - pattern.size() + 1
  • For each index in the pattern
    • If s[offset + index] != pattern[index] then continue from the next offset in the outer loop
  • If the end of the inner loop is reached, then a match was found, return true
• If the end of the outer loop is reached, then there was no match, return false

Putting that into code:

• For each index start in the input string from 0 to word.size() - pattern.size() + 1. The idea here is that near the end of the word when there are not enough characters to match the pattern, stop the loop.
  • For each index in the pattern
    • If word[start + index] != pattern[index] then break out of this inner loop, and continue in the outer loop at start + 1
  • If the end of the inner loop is reached without ever braking out, then a match was found, return true immediately
• If the end of the outer loop is reached, then there was no match, return false

Putting that into code:

bool isSubstr(const std::string & word, const std::string & pattern)
{
    for (auto start = 0; start < word.size() - pattern.size() + 1; start++)
    { 
        bool found = true;
        for (auto i = 0; i < pattern.size(); i++)
        {
            if (word[start + i] != pattern[i])
            {
                found = false;
                break;
            }
        }
        if (found)
        {
            return true;
        }
    }
    return false;
}

To avoid using the flag variable found, we can move the inner loop into a separate function, which instead of setting a flag variable + break, returns false immediately:

Simplify the loop logic

The nested loop in isSubstr is a bit difficult to understand:

• The outer loop variable i can be modified at multiple places. It's simplest when the counter is only modified in the loop statement (i++ in this example).

• It's confusing that the inner loop repeats the i < word.size() condition that's also in the outer loop statement, and yet there is no (explicit) condition on pattern.size(), which intuitively should be important.

The logic would be cleaner using the following algorithm:

• For each index offset in the input string from 0 to s.size() - pattern.size() + 1
  • For each index in the pattern
    • If s[offset + index] != pattern[index] then continue from the next offset in the outer loop
  • If the end of the inner loop is reached, then a match was found, return true
• If the end of the outer loop is reached, then there was no match, return false

Putting that into code:

bool isSubstr(const std::string & s, size_t start, const std::string & pattern)
{
    for (auto i = 0; i < pattern.size(); i++)
    {
        if (s[start + i] != pattern[i])
        {
            return false;
        }
    }
    return true;
}

bool isSubstr(const std::string & word, const std::string & pattern)
{
    for (auto i = 0; i < word.size() - pattern.size() + 1; i++)
    { 
        if (isSubstr(word, i, pattern))
        {
            return true;
        }
    }
    return false;
}

Do not access array elements out of bound

As one of the answers mentioned, pattern[pattIdx] may be out of bounds in this code:

while (i < word.size() && pattern[pattIdx] == word[i])
{
    pattIdx++;
    i++;
} 

Although the code happens to work, this is a bad practice, therefore it's better to avoid. Which is easy enough to do, see the example I have in the previous point.

Simplify the loop logic

The nested loop in isSubstr is a bit difficult to understand:

• The outer loop variable i can be modified at multiple places. It's simplest when the counter is only modified in the loop statement (i++ in this example).

• It's confusing that the inner loop repeats the i < word.size() condition that's also in the outer loop statement, and yet there is no (explicit) condition on pattern.size(), which intuitively should be important.

The logic would be cleaner using the following algorithm:

• For each index offset in the input string from 0 to s.size() - pattern.size() + 1
  • For each index in the pattern
    • If s[offset + index] != pattern[index] then continue from the next offset in the outer loop
  • If the end of the inner loop is reached, then a match was found, return true
• If the end of the outer loop is reached, then there was no match, return false

Putting that into code:

bool isSubstr(const std::string & s, size_t start, const std::string & pattern)
{
    for (auto i = 0; i < pattern.size(); i++)
    {
        if (s[start + i] != pattern[i])
        {
            return false;
        }
    }
    return true;
}

bool isSubstr(const std::string & word, const std::string & pattern)
{
    for (auto i = 0; i < word.size() - pattern.size() + 1; i++)
    { 
        if (isSubstr(word, i, pattern))
        {
            return true;
        }
    }
    return false;
}

Do not access array elements out of bound

As one of the answers mentioned, pattern[pattIdx] may be out of bounds in this code:

while (i < word.size() && pattern[pattIdx] == word[i])
{
    pattIdx++;
    i++;
} 

Although the code happens to work, this is a bad practice, therefore it's better to avoid. Which is easy enough to do, see the example I gave in the previous point.

Simplify the loop logic

The nested loop in isSubstr is a bit difficult to understand:

• The outer loop variable i can be modified at multiple places. It's simplest when the counter is only modified in the loop statement (i++ in this example).

• It's confusing that the inner loop repeats the i < word.size() condition that's also in the outer loop statement, and yet there is no (explicit) condition on pattern.size(), which intuitively should be important.

The logic would be cleaner using the following algorithm:

• For each index offset in the input string from 0 to s.size() - pattern.size() + 1
  • For each index in the pattern
    • If s[offset + index] != pattern[index] then continue from the next offset in the outer loop
  • If the end of the inner loop is reached, then a match was found, return true
• If the end of the outer loop is reached, then there was no match, return false

Putting that into code:

bool isSubstr(const std::string & s, size_t start, const std::string & pattern)
{
    for (auto i = 0; i < pattern.size(); i++)
    {
        if (s[start + i] != pattern[i])
        {
            return false;
        }
    }
    return true;
}

bool isSubstr(const std::string & word, const std::string & pattern)
{
    for (auto i = 0; i < word.size() - pattern.size() + 1; i++)
    { 
        if (isSubstr(word, i, pattern))
        {
            return true;
        }
    }
    return false;
}

Do not access array elements out of bound

As one of the answers mentioned, pattern[pattIdx] may be out of bounds in this code:

while (i < word.size() && pattern[pattIdx] == word[i])
{
    pattIdx++;
    i++;
} 

Although the code happens to work, this is a bad practice, therefore it's better to avoid (see example above).

Simplify the loop logic

The nested loop in isSubstr is a bit difficult to understand:

• The outer loop variable i can be modified at multiple places. It's simplest when the counter is only modified in the loop statement (i++ in this example).

• It's confusing that the inner loop repeats the i < word.size() condition that's also in the outer loop statement, and yet there is no (explicit) condition on pattern.size(), which intuitively should be important.

The logic would be cleaner using the following algorithm:

• For each index offset in the input string from 0 to s.size() - pattern.size() + 1
  • For each index in the pattern
    • If s[offset + index] != pattern[index] then continue from the next offset in the outer loop
  • If the end of the inner loop is reached, then a match was found, return true
• If the end of the outer loop is reached, then there was no match, return false

Putting that into code:

bool isSubstr(const std::string & s, size_t start, const std::string & pattern)
{
    for (auto i = 0; i < pattern.size(); i++)
    {
        if (s[start + i] != pattern[i])
        {
            return false;
        }
    }
    return true;
}

bool isSubstr(const std::string & word, const std::string & pattern)
{
    for (auto i = 0; i < word.size() - pattern.size() + 1; i++)
    { 
        if (isSubstr(word, i, pattern))
        {
            return true;
        }
    }
    return false;
}

Do not access array elements out of bound

As one of the answers mentioned, pattern[pattIdx] may be out of bounds in this code:

while (i < word.size() && pattern[pattIdx] == word[i])
{
    pattIdx++;
    i++;
} 

Although the code happens to work, this is a bad practice, therefore it's better to avoid. Which is easy enough to do, see the example I have in the previous point.