C++与Java记忆化实现单词拆分DP问题结果不一致求助

嘿，我一眼就揪出问题所在了——这和vector还是Java数组完全没关系，核心是C++的string::substr方法和Java的String.substring的参数逻辑天差地别，导致你截取的子串根本不是预期的内容，自然匹配不到字典里的单词。

关键参数差异 #

咱们直接对比两个方法的行为：

• Java的substring(start, end)：取的是从start（包含）到end（不包含）的子串，子串长度是end - start，这正是你循环里想要的逻辑。
• C++的substr(pos, count)：第一个参数是起始位置，第二个参数是要截取的字符总数，不是结束索引！如果省略第二个参数，才会自动截取到字符串末尾。

在你的C++代码里，s.substr(start, end)这行完全错了：比如当start=5、end=8时，你本意是取"pen"（长度3），但这行代码会从索引5开始截取8个字符——这要么超出字符串范围，要么取到一堆无关字符，根本匹配不到字典里的"pen"，递归自然返回false，最终整个结果出错。

修正后的C++代码 #

只需要把循环里的substr参数改成end - start，和Java的逻辑对齐就行：

bool wordBreak(string s, vector<string> &wordDict) {
    vector<int> bArr(s.length(), -1);
    unordered_set<string> set(wordDict.begin(), wordDict.end());
    return wordBreak(s, bArr, 0, set);
}
bool wordBreak(string s, vector<int> &bArr, int start, unordered_set<string> &set) {
    if (start == s.length()) return true;
    // 记忆化缓存直接返回结果
    if (bArr[start] != -1) return (bArr[start] == 1);
    for (int end = start + 1; end <= s.length(); end++) {
        // 修正：substr第二个参数改为子串长度 end - start
        if (set.count(s.substr(start, end - start)) && wordBreak(s, bArr, end, set)) {
            bArr[start] = 1;
            return bArr[start] == 1;
        }
    }
    bArr[start] = 0;
    return false;
}

验证一下 #

拿你的测试用例"applepenapple"来说：

• 当start=0、end=5时，end - start=5，substr(0,5)截取到"apple"，匹配字典；
• 接着start=5、end=8时，end - start=3，substr(5,3)截取到"pen"，匹配字典；
• 最后start=8、end=13时，截取到"apple"，匹配字典，递归走到start=13（等于字符串长度），返回true，整个函数就会正确返回true了。

至于你担心的vector和Java数组的差异，完全不用在意——这里vector的行为和Java的Integer数组完全一致，都是用来做记忆化存储的，不会影响结果。

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