我正在尝试解决Leetcode的 单词阶梯问题。简而言之,题目要求你编写代码,通过每次替换一个字母将一个单词转换为另一个单词,使得每个中间字符串也是一个单词。
我知道使用BFS算法任何人都可以轻松解决它。但我认为动态规划(DP)技术在这里也可以发挥作用。因此,我尝试使用DP解决它。对于每个样例测试用例,它都运行良好。但是当输入变大时(系统评测),该代码会失败。
到目前为止,我仍然不明白为什么DP不能在这里起作用?
请问有人能给我一个小的输入,让这个代码失败吗?你知道很难通过这个大输入进行调试。
提前感谢。
class Solution {
public:
vector<int> dp;
int n;
bool isOneDiff(string str1, string str2) {
if(str1.length() != str2.length()) return false;
int len = str1.length();
int cnt = 0;
for(int i = 0; i < len; i++) {
if(str1[i] != str2[i]) cnt++;
}
return cnt == 1;
}
int solve(string cur, int ind, const string endWord, vector<string> wordList) {
if(cur == endWord) return 1;
int &ret = dp[ind];
if(ret != -1) return ret;
ret = 100000000; // Infinity
for(int i = 0; i < n; i++) {
if(isOneDiff(cur, wordList[i])) {
ret = min(ret, 1 + solve(wordList[i], i, endWord, wordList));
}
}
return ret;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
n = wordList.size();
dp.clear();
dp.resize(n+2, -1);
int res = solve(beginWord, n, endWord, wordList);
if(res >= 100000000) return 0; // if res is greater than or equal to infinity then I have to return 0
return res;
}
};