Leetcode 097 Interleaving String（bfs）

本文主要是介绍Leetcode 097 Interleaving String（bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：Leetcode 097 Interleaving String

解题思路：在队列中维护truple，i和j，表示s1[i], s2[j]匹配到s3[k]，然后k+1在队列的基础上向后匹配。

class Solution {public:bool isInterleave(string s1, string s2, string s3) {int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();if (n1 + n2 != n3) return false;set<pair<int,int>> g;g.insert(make_pair(0, 0));for (int i = 0; i < n3; i++) {set<pair<int,int>> t;for (set<pair<int,int>>::iterator iter = g.begin(); iter != g.end(); iter++) {int x = iter->first;int y = iter->second;if (x < n1 && s1[x] == s3[i])t.insert(make_pair(x+1, y));if (y < n2 && s2[y] == s3[i])t.insert(make_pair(x, y+1));}g = t;}return g.size();}
};

这篇关于Leetcode 097 Interleaving String（bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---