当前位置： 代码网 > it编程>数据库>MsSqlserver > 动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本

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

2024年08月01日 • MsSqlserver •我要评论
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。另给你两个下标从 0 开始的字符串数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符串 original[i] 更改为字符串 changed[i] 的成本。你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] ==

涉及知识点


多源最短路径 字典树

作者推荐

题目

给你两个下标从 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;
		}

//多源码路径
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;
};

分析

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

代码

我写了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();
	}
};

第一版超时

//多源码路径
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;

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学院，听白银讲师（也就是鄙人）的讲解。

如何你想快

速形成战斗了，为老板分忧，请学习c#入职培训、c++入职培训等课程

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： vs2019 c++17
或者 操作系统：win10 开发环境： vs2022 c++17
如无特殊说明，本算法用c++ 实现。

赞 (0)

相关文章:

版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站仅提供信息存储服务，不拥有所有权，不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 2386932994@qq.com 举报，一经查实将立刻删除。

发表评论

验证码：
最近更新的文章
推荐阅读
大家感兴趣的文章
Copyright © 2017-2025  代码网 保留所有权利. 粤ICP备2024248653号
站长QQ:2386932994 | 联系邮箱：2386932994@qq.com