涉及知識點
動態(tài)規(guī)劃匯總
多源最短路徑 字典樹
作者推薦
視頻算法專題
題目
給你兩個下標從 0 開始的字符串 source 和 target ，它們的長度均為 n 并且由 小寫 英文字母組成。
另給你兩個下標從 0 開始的字符串數(shù)組 original 和 changed ，以及一個整數(shù)數(shù)組 cost ，其中 cost[i] 代表將字符串 original[i] 更改為字符串 changed[i] 的成本。
你從字符串 source 開始。在一次操作中，如果 存在 任意 下標 j 滿足 cost[j] == z 、original[j] == x 以及 changed[j] == y ，你就可以選擇字符串中的 子串 x 并以 z 的成本將其更改為 y 。 你可以執(zhí)行 任意數(shù)量 的操作，但是任兩次操作必須滿足 以下兩個 條件 之一 ：
在兩次操作中選擇的子串分別是 source[a…b] 和 source[c…d] ，滿足 b < c 或 d < a 。換句話說，兩次操作中選擇的下標 不相交 。
在兩次操作中選擇的子串分別是 source[a…b] 和 source[c…d] ，滿足 a == c 且 b == d 。換句話說，兩次操作中選擇的下標 相同 。
返回將字符串 source 轉(zhuǎn)換為字符串 target 所需的 最小 成本。如果不可能完成轉(zhuǎn)換，則返回 -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” 轉(zhuǎn)換為 “acbe”，執(zhí)行以下操作：
- 將子串 source[1…1] 從 “b” 改為 “c” ，成本為 5 。
- 將子串 source[2…2] 從 “c” 改為 “e” ，成本為 1 。
- 將子串 source[2…2] 從 “e” 改為 “b” ，成本為 2 。
- 將子串 source[3…3] 從 “d” 改為 “e” ，成本為 20 。
產(chǎn)生的總成本是 5 + 1 + 2 + 20 = 28 。
可以證明這是可能的最小成本。
示例 2：
輸入：source = “abcdefgh”, target = “acdeeghh”, original = [“bcd”,“fgh”,“thh”], changed = [“cde”,“thh”,“ghh”], cost = [1,3,5]
輸出：9
解釋：將 “abcdefgh” 轉(zhuǎn)換為 “acdeeghh”，執(zhí)行以下操作： - 將子串 source[1…3] 從 “bcd” 改為 “cde” ，成本為 1 。
- 將子串 source[5…7] 從 “fgh” 改為 “thh” ，成本為 3 ?？梢詧?zhí)行此操作，因為下標 [5,7] 與第一次操作選中的下標不相交。
- 將子串 source[5…7] 從 “thh” 改為 “ghh” ，成本為 5 ?？梢詧?zhí)行此操作，因為下標 [5,7] 與第一次操作選中的下標不相交，且與第二次操作選中的下標相同。
產(chǎn)生的總成本是 1 + 3 + 5 = 9 。
可以證明這是可能的最小成本。
示例 3：
輸入：source = “abcdefgh”, target = “addddddd”, original = [“bcd”,“defgh”], changed = [“ddd”,“ddddd”], cost = [100,1578]
輸出：-1
解釋：無法將 “abcdefgh” 轉(zhuǎn)換為 “addddddd” 。
如果選擇子串 source[1…3] 執(zhí)行第一次操作，以將 “abcdefgh” 改為 “adddefgh” ，你無法選擇子串 source[3…7] 執(zhí)行第二次操作，因為兩次操作有一個共用下標 3 。
如果選擇子串 source[3…7] 執(zhí)行第一次操作，以將 “abcdefgh” 改為 “abcddddd” ，你無法選擇子串 source[1…3] 執(zhí)行第二次操作，因為兩次操作有一個共用下標 3 。
參數(shù)范圍：
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
分析
將s按順序拆分成若干子串，任何字符都在一個子串中，且只在一個字串中。求這些子串全部轉(zhuǎn)成t的最小成本。
動態(tài)規(guī)劃
| 動態(tài)規(guī)劃之狀態(tài)表示 | dp[i]表示將s[0,i)轉(zhuǎn)化成t[0,i)的最小成本 |
| 動態(tài)規(guī)劃之狀態(tài)轉(zhuǎn)移方程 | dp[j]=min(dp[i]+s[i,j)轉(zhuǎn)化成t[i,j)成本), i取值范圍[0,j) |
| 動態(tài)規(guī)劃之狀態(tài)之初始化 | dp[0]=0 |
| 動態(tài)規(guī)劃之狀態(tài)之填表順序 | 兩層循環(huán)枚舉i,j ，先枚舉i,再枚舉j。s[i,j)是最后一個子串 |
| 動態(tài)規(guī)劃之狀態(tài)之返回值 | dp.back() |
字符經(jīng)過多次轉(zhuǎn)化的最小成本
本質(zhì)就是最短多源路徑。
將字符串轉(zhuǎn)成整數(shù)（節(jié)點編號）
如果用哈希map，每次是O(n)，就超時了。可以自寫哈?；蛴米值錁洌瑥牟樵僺[i,j)到s[i+j+1)時間復雜度是O(1)?？倳r間復雜度是O(n2)。
測試用例
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);
}
代碼
我寫了N版都超時，單個用例不超時，總用例超時。用題解的代碼運行了錯誤和超時用例，速度比我的速度快了近一半。算了，不繼續(xù)優(yōu)化了，許多比賽的技巧是工作的災難，比如用原生數(shù)組代替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中轉(zhuǎn)
for (int i1 = 0; i1 < n; i1++)
{
for (int i2 = 0; i2 < n; i2++)
{
//此時：m_vMat[i1][i2] 表示通過[0,i)中轉(zhuǎn)的最短距離
m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
//m_vMat[i1][i2] 表示通過[0,i]中轉(zhuǎn)的最短距離
}
}
}
};
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();
}
};
第一版超時
//多源碼路徑
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中轉(zhuǎn)
for (int i1 = 0; i1 < n; i1++)
{
for (int i2 = 0; i2 < n; i2++)
{
//此時：m_vMat[i1][i2] 表示通過[0,i)中轉(zhuǎn)的最短距離
m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
//m_vMat[i1][i2] 表示通過[0,i]中轉(zhuǎn)的最短距離
}
}
}
};
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中轉(zhuǎn)
for (int i1 = 0; i1 < n; i1++)
{
for (int i2 = 0; i2 < n; i2++)
{
//此時：m_vMat[i1][i2] 表示通過[0,i)中轉(zhuǎn)的最短距離
m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
//m_vMat[i1][i2] 表示通過[0,i]中轉(zhuǎn)的最短距離
}
}
}
};
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(chǎn)’>
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;
protected:
int m_iLeve=-1;
CTrie* m_vPChilds[iTypeNum] = { nullptr };
};
template<char defData, int iTypeNum = 26, char cBegin = ‘a(chǎn)’>
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(chǎn)’, int iTypeNum = 26, char cBegin = ‘a(chǎn)’>
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中轉(zhuǎn)
for (int i1 = 0; i1 < n; i1++)
{
for (int i2 = 0; i2 < n; i2++)
{
//此時：m_vMat[i1][i2] 表示通過[0,i)中轉(zhuǎn)的最短距離
m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
//m_vMat[i1][i2] 表示通過[0,i]中轉(zhuǎn)的最短距離
}
}
}
};
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();
}
};
擴展閱讀
視頻課程
有效學習：明確的目標 及時的反饋 拉伸區(qū)（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成戰(zhàn)斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176
相關下載
想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想對大家說的話 |
|---|
| 聞缺陷則喜是一個美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。 |
| 子墨子言之：事無終始，無務多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。 |
| 如果程序是一條龍，那算法就是他的是睛 |
測試環(huán)境
操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用C++ 實現(xiàn)。文章來源：http://www.zghlxwxcb.cn/news/detail-761619.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-761619.html
到了這里，關于動態(tài)規(guī)劃 多源路徑 字典樹 LeetCode2977:轉(zhuǎn)換字符串的最小成本的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
