AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本

2024-01-22 65
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 动态规划 多源路径 字典树 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

分析

将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)。

测试用例

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版都超时，单个用例不超时，总用例超时。用题解的代码运行了错误和超时用例，速度比我的速度快了近一半。算了，不继续优化了，许多比赛的技巧是工作的灾难，比如用原生数组代替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();
  }
};

第一版超时

//多源码路径
template10001000>
class CFloyd
{
public:
CFloyd(const 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 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 mStrToNode;
for (int i = 0; i < strs.size(); i++)
{
mStrToNode[strs[i]] = i;
}
const int iNotMay = 1000 * 1000 * 1000;
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();
}
};

第二版超时

//多源码路径
template10001000>
class CFloyd
{
public:
CFloyd(const 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 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 mStrToNode;
for (int i = 0; i < strs.size(); i++)
{
mStrToNode[strs[i]] = i;
}
const int iNotMay = 1000 * 1000 * 1000;
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 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
class CStrTrieHelp
{
public:
CTrie* Add(const string& s,int iDebug)
{
return m_trie.Add(s.begin(), s.begin() + s.length(), iDebug);
}
CTrie* Search(const string& s)
{
return m_trie.Search(s.begin(), s.begin() + s.length());
}
CTrie* SearchSub(const string& s,int iPos,int len)
{
return m_trie.Search(s.begin()+ iPos, s.begin() + iPos + len );
}
CTrie m_trie;
};
template
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 m_trie;
};
//多源码路径
template10001000>
class CFloyd
{
public:
CFloyd(const 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 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 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++ 实现。

文章标签：
测试技术
算法
C++
JavaScript
C#
关键词：
LeetCode字符串
动态规划LeetCode
动态规划LeetCode字符串
LeetCode成本
闻缺陷则喜何志丹
目录
相关文章
iamzfh
|
3月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
iamzfh
41 1
石小浪♪
|
3月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法，通过逆向编号字符串，将乘法运算转化为二维数组的累加过程，最后处理进位并转换为字符串结果，解决了两个大数相乘的问题。
石小浪♪
31 9
石小浪♪
|
3月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法，包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
石小浪♪
24 0
Codelinghu
|
3月前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
Codelinghu
33 0
Codelinghu
|
3月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
Codelinghu
27 0
Codelinghu
|
3月前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
Codelinghu
25 0
Codelinghu
|
3月前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
Codelinghu
22 0
服务端技术栈
|
5月前
|
存储 算法
LeetCode第43题字符串相乘
LeetCode第43题"字符串相乘"的解题方法，通过使用数组存储乘积并处理进位，避免了字符串转换数字的复杂性，提高了算法效率。
服务端技术栈
40 0
LeetCode第43题字符串相乘
服务端技术栈
|
5月前
|
算法 Java
LeetCode第28题找出字符串中第一个匹配项的下标
这篇文章介绍了LeetCode第28题"找出字符串中第一个匹配项的下标"的两种解法：暴力解法和KMP算法，并解释了KMP算法通过构建前缀表来提高字符串搜索的效率。
服务端技术栈
60 0
LeetCode第28题找出字符串中第一个匹配项的下标
服务端技术栈
|
5月前
|
算法
LeetCode第8题字符串转换整数 (atoi)
该文章介绍了 LeetCode 第 8 题字符串转换整数 (atoi)的解法，需要对字符串进行格式解析与校验，去除前导空格和处理正负号，通过从高位到低位的计算方式将字符串转换为整数，并处理越界情况。同时总结了这几道题都需要对数字的表示有理解。
服务端技术栈
41 0
LeetCode第8题字符串转换整数 (atoi)