C++与Java记忆差异[重复]

Question

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 we have a memoized solution to this problem, avoid recurion
    if (bArr[start] != -1)
        return (bArr[start] == 1);
    for (int end = start + 1; end <= s.length(); end++) {
        if (set.count(s.substr(start, end)) && wordBreak(s, bArr, end, set)) {
            bArr[start] = 1;
            return bArr[start] == 1;
        }
    }
    bArr[start] = 0;
    return false;
}

使用Java的工作代码：

public boolean wordBreak(String s, List<String> wordDict) {
    Integer[] memo =new Integer[s.length()];
    Arrays.fill(memo,-1);
    return word_Break(s, new HashSet(wordDict), 0, memo);
}

public boolean word_Break(String s, Set<String> wordDict, int start, Integer[] memo) {
    if (start == s.length()) {
        return true;
    }
    if (memo[start] != -1) {
        return memo[start]==1;
    }
    for (int end = start + 1; end <= s.length(); end++) {
        if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
            memo[start] = 1;
            return memo[start] == 1;
        }
    }
    memo[start] = 0;
    return false;
}

C++代码用dictionary[“Apple”,“Pen”]返回“ApplePenApple”的false，我不知道为什么java返回true是正确的。这两种解决方案之间唯一的主要区别（我认为）是我的C++在java代码中使用向量而不是原生数组。最初，我认为这可能与C++使用自动存储（堆栈）而不是自由存储（堆）有关，这就是为什么我使用向量而不是C样式的数组来避免内存管理，因为RAII。尽管进行了这种更改，但bug仍然存在。有一个更简单的解决方案完全避免递归，但我很好奇为什么C++返回的输出与Java不同。

Answer 1

我看到了一个潜在的问题。来自java.lang.stringJavadoc（强调是我的）：

公共字符串子字符串（int beginIndex,int endIndex）

返回一个新字符串，该字符串是此字符串的子字符串。子字符串从指定的beginIndex开始，并扩展到索引endIndex-1处的字符。因此，子字符串的长度是endindex-beginindex。

"hamburger".substring(4, 8) returns "urge"
"smiles".substring(1, 5) returns "mile"

beginIndex-开始索引，包括在内。

endIndex-结束索引，排他。

来自cpPreference.com字符串文档：

也就是说，在Java中，您应该将索引作为第二个参数传递给string.substring(...)，但是在C++中，您应该将长度传递给basic_string::substr(...)。但是，您正在做：

s.substr(start, end)

和

s.substring(start, end)

在这两种情况下。

s.substr(start, end - start)