97. Interleaving String

題目

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

           

解析

• LeetCode（97） Interleaving String

  狀态cache[i][j]表示，s1的前i個字元和s2的前j個字元是否能交叉構成s3的前i+j個字元

  初始化：

  cache[0][0] = True 因為兩個空字元串可以組成空字元串

  邊界情況是一個字元串為空，初始化隻需判斷另一個字元串和目标字元串前x為是否相等

  遞推關系 cache[i][j] = (s1[i] == s3[i+j] and cache[i-1][j]) or (s2[j] == s3[i+j] and cache[i][j-1])

class Solution_97 {
public:
	bool isInterleave(string s1, string s2, string s3) {

		if (s3.length() != s1.length() + s2.length())
			return false;

		bool table[s1.length() + 1][s2.length() + 1];

		for (int i = 0; i < s1.length() + 1; i++)
		for (int j = 0; j < s2.length() + 1; j++){
			if (i == 0 && j == 0)
				table[i][j] = true;
			else if (i == 0)
				table[i][j] = (table[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
			else if (j == 0)
				table[i][j] = (table[i - 1][j] && s1[i - 1] == s3[i + j - 1]);
			else
				table[i][j] = (table[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (table[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
		}

		return table[s1.length()][s2.length()];
	}
};

           

題目來源

C/C++基本文法學習

STL

C++ primer