- 1网络协议与攻击模拟_01winshark工具简介
- 2git rebase和merge区别_git rebase和merge有什么区别
- 3Android FileProvider的基本使用
- 4mysql分区表之三：MySQL分区建索引[转]
- 5超简单白话文机器学习 - 支持向量机SVM（含算法讲解，公式全解，手写代码实现，调包实现）_支持向量机(svm)
- 6leetcode - [30. 串联所有单词的子串]_leetcode 字串的链接
- 7基于招聘网站的大数据专业相关招聘信息建模与可视化分析_招聘可视化文章
- 8wpf自定义路由事件
- 9C#托管类型与非托管类型的字节数组序列化_c# 托管类型
- 10SparkSQL – Catalyst_sparksql 执行计划
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本_字典树动态规划
赞
踩
涉及知识点
作者推荐
题目
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。
另给你两个下标从 0 开始的字符串数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符串 original[i] 更改为字符串 changed[i] 的成本。
你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y ，你就可以选择字符串中的 子串 x 并以 z 的成本将其更改为 y 。 你可以执行 任意数量 的操作，但是任两次操作必须满足 以下两个 条件 之一 ：
在两次操作中选择的子串分别是 source[a…b] 和 source[c…d] ，满足 b < c 或 d < a 。换句话说，两次操作中选择的下标 不相交 。
在两次操作中选择的子串分别是 source[a…b] 和 source[c…d] ，满足 a == c 且 b == d 。换句话说，两次操作中选择的下标 相同 。
返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。
注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。
示例 1：
输入：source = “abcd”, target = “acbe”, original = [“a”,“b”,“c”,“c”,“e”,“d”], changed = [“b”,“c”,“b”,“e”,“b”,“e”], cost = [2,5,5,1,2,20]
输出：28
解释：将 “abcd” 转换为 “acbe”，执行以下操作：
- 将子串 source[1…1] 从 “b” 改为 “c” ，成本为 5 。
- 将子串 source[2…2] 从 “c” 改为 “e” ，成本为 1 。
- 将子串 source[2…2] 从 “e” 改为 “b” ，成本为 2 。
- 将子串 source[3…3] 从 “d” 改为 “e” ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。
可以证明这是可能的最小成本。
示例 2：
输入：source = “abcdefgh”, target = “acdeeghh”, original = [“bcd”,“fgh”,“thh”], changed = [“cde”,“thh”,“ghh”], cost = [1,3,5]
输出：9
解释：将 “abcdefgh” 转换为 “acdeeghh”，执行以下操作： - 将子串 source[1…3] 从 “bcd” 改为 “cde” ，成本为 1 。
- 将子串 source[5…7] 从 “fgh” 改为 “thh” ，成本为 3 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交。
- 将子串 source[5…7] 从 “thh” 改为 “ghh” ，成本为 5 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交，且与第二次操作选中的下标相同。
产生的总成本是 1 + 3 + 5 = 9 。
可以证明这是可能的最小成本。
示例 3：
输入：source = “abcdefgh”, target = “addddddd”, original = [“bcd”,“defgh”], changed = [“ddd”,“ddddd”], cost = [100,1578]
输出：-1
解释：无法将 “abcdefgh” 转换为 “addddddd” 。
如果选择子串 source[1…3] 执行第一次操作，以将 “abcdefgh” 改为 “adddefgh” ，你无法选择子串 source[3…7] 执行第二次操作，因为两次操作有一个共用下标 3 。
如果选择子串 source[3…7] 执行第一次操作，以将 “abcdefgh” 改为 “abcddddd” ，你无法选择子串 source[1…3] 执行第二次操作，因为两次操作有一个共用下标 3 。
参数范围：
1 <= source.length == target.length <= 1000
source、target 均由小写英文字母组成
1 <= cost.length == original.length == changed.length <= 100
1 <= original[i].length == changed[i].length <= source.length
original[i]、changed[i] 均由小写英文字母组成
original[i] != changed[i]
1 <= cost[i] <= 106
2024年3月17补充
看了题解，自己也尝试了一下，终于找到周赛时，超时的原因了。加上这个判断，用时减少90%。
if (INF == m_vMat[i1][i])
{
continue;
}
- 1
- 2
- 3
- 4
//多源码路径 template<class T, T INF = 1000 * 1000 * 1000> class CFloyd { public: CFloyd(const vector<vector<T>>& mat) { m_vMat = mat; const int n = mat.size(); for (int i = 0; i < n; i++) {//通过i中转 for (int i1 = 0; i1 < n; i1++) { if (INF == m_vMat[i1][i]) { continue; } for (int i2 = 0; i2 < n; i2++) { //此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离 m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]); //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离 } } } }; vector<vector<T>> m_vMat; };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
分析
将s按顺序拆分成若干子串，任何字符都在一个子串中，且只在一个字串中。求这些子串全部转成t的最小成本。
动态规划
| 动态规划之状态表示 | dp[i]表示将s[0,i)转化成t[0,i)的最小成本 |
| 动态规划之状态转移方程 | dp[j]=min(dp[i]+s[i,j)转化成t[i,j)成本), i取值范围[0,j) |
| 动态规划之状态之初始化 | dp[0]=0 |
| 动态规划之状态之填表顺序 | 两层循环枚举i,j ，先枚举i,再枚举j。s[i,j)是最后一个子串 |
| 动态规划之状态之返回值 | dp.back() |
字符经过多次转化的最小成本
本质就是最短多源路径。
将字符串转成整数（节点编号）
如果用哈希map，每次是O(n)，就超时了。可以自写哈希或用字典树，从查询s[i,j)到s[i+j+1)时间复杂度是O(1)。总时间复杂度是O(n2)。
2024年3月4号补充
三个难点：
一，字符串编码，字典树。
二，s[i,j)交换多次，多源最短路径。
三，相等可以理解成本为0。可转化成 k连续区间最小值。
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string source, target; vector<string> original, changed; vector<int> cost; { Solution sln; source = "abcdefgh", target = "acdeeghh", original = { "bcd", "fgh", "thh" }, changed = { "cde", "thh", "ghh" }, cost = { 1, 3, 5 }; auto res = sln.minimumCost(source, target, original, changed, cost); Assert(9LL, res); } { Solution sln; source = "abcd", target = "acbe"; original = { "a", "b", "c", "c", "e", "d" }, changed = { "b", "c", "b", "e", "b", "e" }; cost = { 2, 5, 5, 1, 2, 20 }; auto res = sln.minimumCost(source, target, original, changed, cost); Assert(28LL, res); } { Solution sln; source = "abbaacddcbacbddcbdbddcadbadbbdbaabcdbdbdcaccacaddcabadadaccabbddbbdacaacdbdcaaddcacbcbcaaacaddabcabc"; target = "abbaacdbcbabcadcbdbddcadbadbbddaabcdbdddcacadbacabcbdbbbbdaabbddbbdaabbcdbdcaaddcacbcbcadadccdcbcbcb"; original = { "b", "c", "a", "cbd", "adc", "ddb", "dcb", "dbd", "b", "caac", "acdc", "cbbd", "bcdb", "ddbc", "aacadda", "cbadbbd", "aaabcad", "bacdccc", "ddabdaa", "abc", "bbc", "cdd", "ddb", "cacaddcabad", "bdcdccabdcb", "bddbbabdcac", "adacc", "bbdca", "dabad", "cddcba" }; changed = { "c", "a", "d", "adc", "ddb", "dcb", "dbd", "bca", "d", "acdc", "cbbd", "bcdb", "ddbc", "abbc", "cbadbbd", "aaabcad", "bacdccc", "ddabdaa", "dadccdc", "bbc", "cdd", "ddb", "bcb", "bdcdccabdcb", "bddbbabdcac", "adbacabcbdb", "bbdca", "dabad", "bbbda", "cdbcba" }; cost = { 63, 87, 77, 94, 100, 73, 99, 16, 89, 94, 76, 43, 76, 84, 83, 38, 96, 87, 34, 98, 33, 53, 58, 90, 61, 51, 92, 76, 91, 70 }; auto res = sln.minimumCost(source, target, original, changed, cost); Assert(2044LL, res); } { Solution sln; source = "aaaddcaaccbabaaccbabbaadcccadbaacbddbaccabddbdbaaddbbacbddddbbdbccaadcaccacdbcbddbacabadaaccbadbbdbc"; target = "abaddcabcdbabcbadcaccaadabbadddbcacaaabdabbdcbbdbcbaaabbbcddcbddcbccadacddcbdcbacadbbadbdabcbadbbdac"; original = { "ddddb", "dccbb", "dadac", "dbdbb", "ddbacabadaac", "bcbccdcadabd", "dacabcdaacca", "dcdadacacbbd", "dcccadbaacbddbacc", "dcdcbccdccdbaaaac", "bbbcccdbcdcadaabc", "bccaadcaccacdb", "bbcabcbcbaddbd", "dbadadaddcddad", "badaddbcddacca", "bc", "da", "cb", "ddbdbaaddbbac", "dbcadcdbabddd", "abdadacbbbcca", "adaaabcabdbcc", "caaccbabaaccbabba", "abaadddbaaccbbacc", "bbddaaadcbccccbac", "cdbdbddaadbbbdbdd", "bcbdaabaddbdcdcaa", "aa", "cb", "dd" }; changed = { "dccbb", "dadac", "dbdbb", "bcddc", "bcbccdcadabd", "dacabcdaacca", "dcdadacacbbd", "acadbbadbdab", "dcdcbccdccdbaaaac", "bbbcccdbcdcadaabc", "dabbadddbcacaaabd", "bbcabcbcbaddbd", "dbadadaddcddad", "badaddbcddacca", "dcbccadacddcbd", "da", "cb", "ac", "dbcadcdbabddd", "abdadacbbbcca", "adaaabcabdbcc", "bdcbbdbcbaaab", "abaadddbaaccbbacc", "bbddaaadcbccccbac", "cdbdbddaadbbbdbdd", "bcbdaabaddbdcdcaa", "cabcdbabcbadcacca", "cb", "dd", "ba" }; cost = { 67, 56, 64, 83, 100, 73, 95, 97, 100, 98, 20, 92, 58, 70, 95, 77, 95, 93, 69, 92, 77, 53, 96, 68, 83, 96, 93, 64, 81, 100 }; auto res = sln.minimumCost(source, target, original, changed, cost); Assert(2405LL, res); } //CConsole::Out(res); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
代码
我写了N版都超时，单个用例不超时，总用例超时。用题解的代码运行了错误和超时用例，速度比我的速度快了近一半。算了，不继续优化了，许多比赛的技巧是工作的灾难，比如用原生数组代替vector。
第六版超时
template<class TData, TData defData,int iTypeNum = 26, TData cBegin = 'a'> class CTrie { public: CTrie() { m_iID = s_ID++; } int GetLeadCount() { return m_iLeafCount; } template<class IT> int Add(IT begin, IT end) { int iLeve = 0; CTrie* pNode = this; for (; begin != end; ++begin) { pNode = pNode->AddChar(*begin); pNode->m_iLeve = iLeve++; } if (-1 == pNode->m_iLeafID) { pNode->m_iLeafID = m_iLeafCount++; } return pNode->m_iLeafID; } template<class IT> CTrie* Search(IT begin, IT end) { if (begin == end) { return this; } if ('.' == *begin) { for (auto& ptr : m_vPChilds) { if (!ptr) { continue; } auto pSearch = ptr->Search(begin + 1, end); if (pSearch) { return pSearch; } } return nullptr; } auto ptr = GetChild(*begin); if (nullptr == ptr) { return nullptr; } return ptr->Search(begin + 1, end); } TData m_data = defData; CTrie* AddChar(TData ele) { if ((ele < cBegin) || (ele >= cBegin + iTypeNum)) { return nullptr; } const int index = ele - cBegin; auto ptr = m_vPChilds[index]; if (!ptr) { m_vPChilds[index] = new CTrie(); } return m_vPChilds[index]; } CTrie* GetChild(TData ele)const { if ((ele < cBegin) || (ele >= cBegin + iTypeNum)) { return nullptr; } return m_vPChilds[ele - cBegin]; } protected: int m_iID; public: int m_iLeafID=-1; protected: int m_iLeve=-1; inline static int s_ID = 0; int m_iLeafCount = 0; CTrie* m_vPChilds[iTypeNum] = { nullptr }; }; template<char defData='a', int iTypeNum = 26, char cBegin = 'a'> class CStrTrieHelp { public: int Add(const string& s) { return m_trie.Add(s.begin(), s.begin() + s.length()); } CTrie<char, defData, iTypeNum, cBegin>* Search(const string& s) { return m_trie.Search(s.begin(), s.begin() + s.length()); } CTrie<char, defData, iTypeNum, cBegin>* SearchSub(const string& s,int iPos,int len) { return m_trie.Search(s.begin()+ iPos, s.begin() + iPos + len ); } CTrie<char, defData, iTypeNum, cBegin> m_trie; }; template<char defData = 'a', int iTypeNum = 26, char cBegin = 'a'> class CStrIndexs { public: void Add(const string& s) { m_trie.Add(s); } int Seach(const string& s) { auto p = m_trie.Search(s); if (nullptr == p) { return -1; } return p->m_iLeafID; } int SearchSub(const string& s, int iPos, int len) { auto p = m_trie.SearchSub(s, iPos, len); if (nullptr == p) { return -1; } return p->m_iDebug; } CStrTrieHelp<defData, iTypeNum, cBegin> m_trie; }; //多源码路径 template<class T,T INF = 1000*1000*1000> class CFloyd { public: CFloyd(const vector<vector<T>>& mat) { m_vMat = mat; const int n = mat.size(); for (int i = 0; i < n; i++) {//通过i中转 for (int i1 = 0; i1 < n; i1++) { for (int i2 = 0; i2 < n; i2++) { //此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离 m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]); //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离 } } } }; vector<vector<T>> m_vMat; }; class Solution { public: long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) { CStrIndexs strIndexs; for (const auto& s : original) { strIndexs.Add(s); } for (const auto& s : changed) { strIndexs.Add(s); } const int iNotMay = 1000 * 1000 * 1000; vector<vector<int>> vMat(strIndexs.m_trie.m_trie.GetLeadCount(), vector<int>(strIndexs.m_trie.m_trie.GetLeadCount(), iNotMay)); for (int j = 0; j < original.size(); j++) { const int iSrc = strIndexs.Seach(original[j]); const int iDest = strIndexs.Seach(changed[j]); auto& n = vMat[iSrc][iDest]; n = min(n, cost[j]); } for (int i = 0; i < strIndexs.m_trie.m_trie.GetLeadCount(); i++) { vMat[i][i] = 0; } CFloyd floyd(vMat); vector<long long> vRet(source.length() + 1, LLONG_MAX / 1000); vRet[0] = 0; for (int i = 0; i < source.length(); i++) { bool bSame = true; auto pSrc = &strIndexs.m_trie.m_trie; auto pDst = &strIndexs.m_trie.m_trie; for (int len = 1; len + i <= source.length(); len++) { const char ch1 = source[len + i - 1]; const char ch2 = target[len + i - 1]; bSame &= (ch1 == ch2); if (nullptr != pSrc) { pSrc = pSrc->GetChild(ch1); } if (nullptr != pDst) { pDst = pDst->GetChild(ch2); } if (bSame) { vRet[i + len] = min(vRet[i + len], vRet[i]); continue; } if ((nullptr == pSrc) || (nullptr == pDst)) { break; } const int iSrc = pSrc->m_iLeafID; const int iDest = pDst->m_iLeafID; if ((-1 == iSrc) || (-1== iDest)) { continue; } const int iDist = floyd.m_vMat[iSrc][iDest]; if (iDist >= iNotMay) { continue; } vRet[i + len] = min(vRet[i + len], vRet[i] + iDist); } } return (vRet.back() >= LLONG_MAX / 1000) ? -1 : vRet.back(); } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
第一版超时
//多源码路径
template<class T,T INF = 100010001000>
class CFloyd
{
public:
CFloyd(const vector<vector>& mat)
{
m_vMat = mat;
const int n = mat.size();
for (int i = 0; i < n; i++)
{//通过i中转
for (int i1 = 0; i1 < n; i1++)
{
for (int i2 = 0; i2 < n; i2++)
{
//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
}
}
}
};
vector<vector> m_vMat;
};
class Solution {
public:
long long minimumCost(string source, string target, vector& original, vector& changed, vector& cost) {
vector strs(original.begin(), original.end());
strs.insert(strs.end(), changed.begin(), changed.end());
sort(strs.begin(),strs.end());
strs.erase(std::unique(strs.begin(), strs.end()), strs.end());
std::unordered_map<string, int> mStrToNode;
for (int i = 0; i < strs.size(); i++)
{
mStrToNode[strs[i]] = i;
}
const int iNotMay = 1000 * 1000 * 1000;
vector<vector> vMat(strs.size(), vector(strs.size(), iNotMay));
vector vOriNode;
for (int j = 0; j < original.size(); j++)
{
vOriNode.emplace_back(mStrToNode[original[j]]);
auto& n = vMat[vOriNode.back()][mStrToNode[changed[j]]];
n = min(n,cost[j]);
}
for (int i = 0; i < strs.size(); i++)
{
vMat[i][i] = 0;
}
CFloyd floyd(vMat);
vector vRet(source.length() + 1,LLONG_MAX/1000 );
vRet[0]=0;
for (int i = 0; i < source.length(); i++)
{
if (source[i] == target[i])
{
vRet[i + 1] = min(vRet[i+1],vRet[i]);
//continue; 相等也可以替换
}
for (int j = 0; j < original.size(); j++)
{
const int len = original[j].length();
if (i + len > source.length())
{
continue;
}
if (source.substr(i, len) != original[j])
{
continue;
}
string sDst = target.substr(i, len);
if (!mStrToNode.count(sDst))
{
continue;
}
const int iDest = mStrToNode[sDst];
const int iDist = floyd.m_vMat[vOriNode[j]][iDest];
if (iDist >= iNotMay)
{
continue;
}
vRet[i + len] = min(vRet[i + len],vRet[i]+iDist);
}
}
return (vRet.back() >= LLONG_MAX / 1000) ? -1 : vRet.back();
}
};
第二版超时
//多源码路径
template<class T,T INF = 100010001000>
class CFloyd
{
public:
CFloyd(const vector<vector>& mat)
{
m_vMat = mat;
const int n = mat.size();
for (int i = 0; i < n; i++)
{//通过i中转
for (int i1 = 0; i1 < n; i1++)
{
for (int i2 = 0; i2 < n; i2++)
{
//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
}
}
}
};
vector<vector> m_vMat;
};
class Solution {
public:
long long minimumCost(string source, string target, vector& original, vector& changed, vector& cost) {
vector strs(original.begin(), original.end());
strs.insert(strs.end(), changed.begin(), changed.end());
sort(strs.begin(),strs.end());
strs.erase(std::unique(strs.begin(), strs.end()), strs.end());
std::unordered_map<string, int> mStrToNode;
for (int i = 0; i < strs.size(); i++)
{
mStrToNode[strs[i]] = i;
}
const int iNotMay = 1000 * 1000 * 1000;
vector<vector> vMat(strs.size(), vector(strs.size(), iNotMay));
for (int j = 0; j < original.size(); j++)
{
auto& n = vMat[mStrToNode[original[j]]][mStrToNode[changed[j]]];
n = min(n,cost[j]);
}
for (int i = 0; i < strs.size(); i++)
{
vMat[i][i] = 0;
}
CFloyd floyd(vMat);
vector vRet(source.length() + 1,LLONG_MAX/1000 );
vRet[0]=0;
for (int i = 0; i < source.length(); i++)
{
for (int len = 1; len + i <= source.length(); len++)
{
const string sSrc = source.substr(i, len);
const string sDst = target.substr(i, len);
if (sSrc == sDst)
{
vRet[i + len] = min(vRet[i + len], vRet[i] );
continue;
}
if (!mStrToNode.count(sDst)|| !mStrToNode.count(sSrc))
{
continue;
}
const int iSrc = mStrToNode[sSrc];
const int iDest = mStrToNode[sDst];
const int iDist = floyd.m_vMat[iSrc][iDest];
if (iDist >= iNotMay)
{
continue;
}
vRet[i + len] = min(vRet[i + len], vRet[i] + iDist);
}
}
return (vRet.back() >= LLONG_MAX / 1000) ? -1 : vRet.back();
}
};
第四版超时
template<class TData, TData defData,int iTypeNum = 26, TData cBegin = ‘a’>
class CTrie
{
public:
CTrie()
{
} template<class IT> CTrie* Add(IT begin, IT end,const int iDebug) { int iLeve = 0; CTrie* pNode = this; for (; begin != end; ++begin) { pNode = pNode->AddChar(*begin); pNode->m_iLeve = iLeve++; } pNode->m_iDebug = iDebug; return pNode; } template<class IT> CTrie* Search(IT begin, IT end) { if (begin == end) { return this; } if ('.' == *begin) { for (auto& ptr : m_vPChilds) { if (!ptr) { continue; } auto pSearch = ptr->Search(begin + 1, end); if (pSearch) { return pSearch; } } return nullptr; } auto ptr = GetChild(*begin); if (nullptr == ptr) { return nullptr; } return ptr->Search(begin + 1, end); } TData m_data = defData; CTrie* AddChar(TData ele) { if ((ele < cBegin) || (ele >= cBegin + iTypeNum)) { return nullptr; } const int index = ele - cBegin; auto ptr = m_vPChilds[index]; if (!ptr) { m_vPChilds[index] = new CTrie(); } return m_vPChilds[index]; } CTrie* GetChild(TData ele)const { if ((ele < cBegin) || (ele >= cBegin + iTypeNum)) { return nullptr; } return m_vPChilds[ele - cBegin]; } int m_iDebug=-1;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
protected:
int m_iLeve=-1;
CTrie* m_vPChilds[iTypeNum] = { nullptr };
};
template<char defData, int iTypeNum = 26, char cBegin = ‘a’>
class CStrTrieHelp
{
public:
CTrie<char, defData, iTypeNum, cBegin>* Add(const string& s,int iDebug)
{
return m_trie.Add(s.begin(), s.begin() + s.length(), iDebug);
}
CTrie<char, defData, iTypeNum, cBegin>* Search(const string& s)
{
return m_trie.Search(s.begin(), s.begin() + s.length());
}
CTrie<char, defData, iTypeNum, cBegin>* SearchSub(const string& s,int iPos,int len)
{
return m_trie.Search(s.begin()+ iPos, s.begin() + iPos + len );
}
CTrie<char, defData, iTypeNum, cBegin> m_trie;
};
template<char defData = ‘a’, int iTypeNum = 26, char cBegin = ‘a’>
class CStrIndexs
{
public:
void Add(const string& s, int iDebug)
{
m_trie.Add(s, iDebug);
}
int Seach(const string& s)
{
auto p = m_trie.Search(s);
if (nullptr == p)
{
return -1;
}
return p->m_iDebug;
}
int SearchSub(const string& s, int iPos, int len)
{
auto p = m_trie.SearchSub(s, iPos, len);
if (nullptr == p)
{
return -1;
}
return p->m_iDebug;
}
protected:
CStrTrieHelp<defData, iTypeNum, cBegin> m_trie;
};
//多源码路径
template<class T,T INF = 100010001000>
class CFloyd
{
public:
CFloyd(const vector<vector>& mat)
{
m_vMat = mat;
const int n = mat.size();
for (int i = 0; i < n; i++)
{//通过i中转
for (int i1 = 0; i1 < n; i1++)
{
for (int i2 = 0; i2 < n; i2++)
{
//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
}
}
}
};
vector<vector> m_vMat;
};
class Solution {
public:
long long minimumCost(string source, string target, vector& original, vector& changed, vector& cost) {
vector strs(original.begin(), original.end());
strs.insert(strs.end(), changed.begin(), changed.end());
sort(strs.begin(), strs.end());
strs.erase(std::unique(strs.begin(), strs.end()), strs.end());
CStrIndexs strIndexs;
for (int i = 0; i < strs.size(); i++)
{
strIndexs.Add(strs[i], i);
}
const int iNotMay = 1000 * 1000 * 1000;
vector<vector> vMat(strs.size(), vector(strs.size(), iNotMay));
for (int j = 0; j < original.size(); j++)
{
const int iSrc = strIndexs.Seach(original[j]);
const int iDest = strIndexs.Seach(changed[j]);
auto& n = vMat[iSrc][iDest];
n = min(n, cost[j]);
}
for (int i = 0; i < strs.size(); i++)
{
vMat[i][i] = 0;
}
CFloyd floyd(vMat);
vector vRet(source.length() + 1, LLONG_MAX / 1000);
vRet[0] = 0;
for (int i = 0; i < source.length(); i++)
{
bool bSame = true;
for (int len = 1; len + i <= source.length(); len++)
{
bSame &= (source[len + i - 1] == target[len + i - 1]);
if (bSame)
{
vRet[i + len] = min(vRet[i + len], vRet[i]);
continue;
}
const int iSrc = strIndexs.SearchSub(source, i, len);
const int iDest = strIndexs.SearchSub(target, i, len);
if ((-1 == iSrc) || (-1== iDest))
{
continue;
}
const int iDist = floyd.m_vMat[iSrc][iDest];
if (iDist >= iNotMay)
{
continue;
}
vRet[i + len] = min(vRet[i + len], vRet[i] + iDist);
}
}
return (vRet.back() >= LLONG_MAX / 1000) ? -1 : vRet.back();
}
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。
