布尔条件检查触发运行时错误？LeetCode单词拆分问题求助

我在解决单词拆分问题时，编写了如下C++代码：

bool existsInDict(string s, vector<string>& wordDict)
{
    if(std::find(wordDict.begin(),wordDict.end(),s) != wordDict.end())
    {
        return true;
    }
    return false;
}

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int str_size = s.length();
        if(str_size == 0)
        return true;

        bool *dict = new bool[str_size+1];
        std::fill(dict, dict+str_size,false);

        for(int i =1;i<=str_size;++i)
        {
            if(dict[i]==false && existsInDict(s.substr(0,i),wordDict))
            {
                dict[i] = true;
            }
            if(dict[i]==true)
            {
                if(i==str_size)
                return true;
                for(int j=i+1;j<=str_size;++j)
                {
                    if((dict[j]==false) && existsInDict(s.substr(i+1,j-i),wordDict))
                    {
                        dict[j] = true;
                    }
                    if((dict[j]==true) && (j == str_size))
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

运行时触发错误：
Line 40: Char 25: runtime error: load of value 190, which is not a valid value for type 'bool' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:49:25

错误原因分析 #

1. 未初始化的布尔数组元素
   代码中用new bool[str_size+1]分配了长度为str_size+1的布尔数组，但std::fill(dict, dict+str_size,false)只填充了前str_size个元素，最后一个元素dict[str_size]处于未初始化状态，存储的是内存中的垃圾值。当循环中i等于str_size时，会读取dict[str_size]，触发未定义行为，导致读取到无效的布尔值。

2. 字符串截取参数错误
   内层循环中substr(i+1,j-i)的起始索引错误，substr的第一个参数是起始位置，第二个是子串长度。这里应该从索引i开始截取长度为j-i的子串，否则会跳过当前分割点后的第一个字符，导致子串匹配错误。

修复方案 #

1. 修正数组填充范围，确保所有元素都被初始化：
   将std::fill(dict, dict+str_size,false)改为std::fill(dict, dict+str_size+1,false)。

2. 修正字符串截取的起始索引：
   将s.substr(i+1,j-i)改为s.substr(i, j-i)。

修复后的代码 #

bool existsInDict(string s, vector<string>& wordDict)
{
    return std::find(wordDict.begin(), wordDict.end(), s) != wordDict.end();
}

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int str_size = s.length();
        if(str_size == 0)
            return true;

        bool *dict = new bool[str_size+1];
        std::fill(dict, dict+str_size+1, false);

        for(int i = 1; i <= str_size; ++i)
        {
            if(!dict[i] && existsInDict(s.substr(0, i), wordDict))
            {
                dict[i] = true;
            }
            if(dict[i])
            {
                if(i == str_size)
                    return true;
                for(int j = i+1; j <= str_size; ++j)
                {
                    if(!dict[j] && existsInDict(s.substr(i, j-i), wordDict))
                    {
                        dict[j] = true;
                    }
                    if(dict[j] && j == str_size)
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

另外，也可以用vector<bool>替代手动分配的数组，避免内存管理和初始化问题，代码会更简洁安全：

bool existsInDict(const string& s, const vector<string>& wordDict)
{
    return std::find(wordDict.begin(), wordDict.end(), s) != wordDict.end();
}

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int str_size = s.length();
        if(str_size == 0)
            return true;

        vector<bool> dict(str_size + 1, false);

        for(int i = 1; i <= str_size; ++i)
        {
            if(!dict[i] && existsInDict(s.substr(0, i), wordDict))
            {
                dict[i] = true;
            }
            if(dict[i])
            {
                if(i == str_size)
                    return true;
                for(int j = i+1; j <= str_size; ++j)
                {
                    if(!dict[j] && existsInDict(s.substr(i, j-i), wordDict))
                    {
                        dict[j] = true;
                    }
                    if(dict[j] && j == str_size)
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

内容的提问来源于stack exchange，提问作者Invictus