C++ 与 Java 记忆差异

Question

所以我一直在尝试解决分词动态规划问题，这基本上意味着给定一个字符串字典和一个字符串，看看字典中的单词是否可以组合成字符串。例如，给定单词 "applepenapple" 和字典 ["apple","pen"] 它应该 return 为真。

我有一个有效的 java 解决方案，但我正在努力提高我的 C++ 技能。我的问题是，尽管我的代码看起来与 Java 中的工作解决方案非常相似，但我没有通过小众测试用例，而且我无法弄清楚原因。

C++代码：

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;
}

对于 "applepenapple" 和字典 ["apple","pen"]，C++ 代码 returning false 我不知道为什么 java return true 哪个是正确的。这两种解决方案之间唯一的主要区别（我认为）是我的 C++ 在 java 代码中使用向量而不是本机数组。最初我认为这可能与使用自动存储（堆栈）与自由存储（堆）的 C++ 有关，这就是为什么我使用向量而不是 C 样式数组来避免 RAII 的内存管理。尽管有此更改，错误仍然存在。有一个更简单的解决方案可以完全避免递归，但我很好奇为什么 C++ return 的输出与 java 不同。

Answer 1

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

public String substring(int beginIndex, int endIndex)

Returns a new string that is a substring of this string. The substring begins at the specified beginIndex and extends to the character at index endIndex - 1. Thus the length of the substring is endIndex-beginIndex.

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

beginIndex - the beginning index, inclusive.

endIndex - the ending index, exclusive.

来自 cppreference.com documentation on strings:

basic_string substr( size_type pos = 0, size_type count = npos ) const;

Returns a substring [pos, pos+count). If the requested substring extends past the end of the string, or if count == npos, the returned substring is [pos, size()).

Parameters

pos - position of the first character to include

count - length of the substring

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

s.substr(start, end)

和

s.substring(start, end)

在这两种情况下。

可能将 C++ 调用调整为

s.substr(start, end - start)

有用吗？

C++ 与 Java 记忆差异

C++ vs Java Memoization Discrepancy

java

c++

recursion

dynamic-programming

memoization