Hard
题目描述
给定两个字符串 str1 和 str2，长度分别为 n 和 m。
如果一个长度为 n + m - 1 的字符串 word 对于每个索引 0 <= i <= n - 1 都满足以下条件，则称它是由 str1 和 str2 生成的：
- 如果
str1[i] == 'T'，则从索引i开始长度为m的子串等于str2，即word[i..(i + m - 1)] == str2。 - 如果
str1[i] == 'F'，则从索引i开始长度为m的子串不等于str2，即word[i..(i + m - 1)] != str2。
返回可以由 str1 和 str2 生成的字典序最小的字符串。如果无法生成任何字符串，返回空字符串 ""。
示例 1：
输入：str1 = "TFTF", str2 = "ab"
输出："ababa"
解释：
下表表示字符串 "ababa"
索引 T/F 长度为 m 的子串
0 'T' "ab"
1 'F' "ba"
2 'T' "ab"
3 'F' "ba"
字符串 "ababa" 和 "ababb" 都可以由 str1 和 str2 生成。
返回 "ababa"，因为它字典序更小。
示例 2：
输入：str1 = "TFTF", str2 = "abc"
输出：""
解释：
无法生成满足条件的字符串。
示例 3：
输入：str1 = "F", str2 = "d"
输出："a"
约束条件：
1 <= n == str1.length <= 10^41 <= m == str2.length <= 500str1仅包含 ‘T’ 或 ‘F’str2仅包含小写英文字母
解题思路
这道题需要构造一个字符串，使其满足模式匹配的约束条件，并且字典序最小。
核心思路：
- 使用动态规划 + KMP算法的思想
- 状态定义：
dp[i][j]表示已经确定了前i个字符，且当前后缀与str2的前缀匹配长度为j的情况下，是否可能构造出有效解 - 对于每个位置，我们贪心地选择字典序最小的字符
关键观察：
- 当
str1[i] == 'T'时，从位置i开始的长度为m的子串必须等于str2 - 当
str1[i] == 'F'时，从位置i开始的长度为m的子串必须不等于str2 - 我们需要使用KMP的 failure function 来高效地处理字符串匹配
算法步骤：
- 预处理
str2的 failure function - 使用动态规划，状态为
(位置, 当前匹配长度) - 对每个位置贪心选择最小的可行字符
- 检查所有约束是否满足
由于字符集只有小写字母，我们可以从 ‘a’ 开始尝试每个字符，选择第一个满足条件的。
代码实现
class Solution {
public:
string generateString(string str1, string str2) {
int n = str1.size(), m = str2.size();
// KMP failure function
vector<int> lps(m, 0);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && str2[i] != str2[j]) j = lps[j - 1];
if (str2[i] == str2[j]) j++;
lps[i] = j;
}
// DP state: dp[pos][match_len] = possible
vector<vector<bool>> dp(n + m, vector<bool>(m + 1, false));
dp[0][0] = true;
string result(n + m - 1, 'a');
for (int pos = 0; pos < n + m - 1; pos++) {
for (char c = 'a'; c <= 'z'; c++) {
bool valid = false;
for (int prevMatch = 0; prevMatch <= m && prevMatch <= pos; prevMatch++) {
if (!dp[pos][prevMatch]) continue;
int newMatch = prevMatch;
while (newMatch > 0 && str2[newMatch] != c) {
newMatch = lps[newMatch - 1];
}
if (str2[newMatch] == c) newMatch++;
// Check constraints
bool canUse = true;
for (int i = 0; i < n; i++) {
if (pos - i >= 0 && pos - i < m) {
if (str1[i] == 'T') {
if (pos - i == m - 1) {
canUse &= (newMatch == m);
}
} else {
if (pos - i == m - 1) {
canUse &= (newMatch != m);
}
}
}
}
if (canUse) {
dp[pos + 1][newMatch] = true;
valid = true;
}
}
if (valid) {
result[pos] = c;
break;
}
}
if (result[pos] == 'a') {
bool hasValidChar = false;
for (char c = 'a'; c <= 'z'; c++) {
bool valid = false;
for (int prevMatch = 0; prevMatch <= m && prevMatch <= pos; prevMatch++) {
if (!dp[pos][prevMatch]) continue;
valid = true;
break;
}
if (valid) {
hasValidChar = true;
break;
}
}
if (!hasValidChar) return "";
}
}
return result;
}
};
class Solution:
def generateString(self, str1: str, str2: str) -> str:
n, m = len(str1), len(str2)
# KMP failure function
lps = [0] * m
j = 0
for i in range(1, m):
while j > 0 and str2[i] != str2[j]:
j = lps[j - 1]
if str2[i] == str2[j]:
j += 1
lps[i] = j
# DP with memoization
from functools import lru_cache
@lru_cache(None)
def canGenerate(pos, match_len):
if pos == n + m - 1:
return True
for c in 'abcdefghijklmnopqrstuvwxyz':
new_match = match_len
while new_match > 0 and str2[new_match] != c:
new_match = lps[new_match - 1]
if str2[new_match] == c:
new_match += 1
valid = True
# Check constraints
for i in range(n):
window_end = pos - i
if 0 <= window_end < m:
if str1[i] == 'T' and window_end == m - 1:
valid &= (new_match == m)
elif str1[i] == 'F' and window_end == m - 1:
valid &= (new_match != m)
if valid and canGenerate(pos + 1, new_match):
return True
return False
if not canGenerate(0, 0):
return ""
result = []
match_len = 0
for pos in range(n + m - 1):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_match = match_len
while new_match > 0 and str2[new_match] != c:
new_match = lps[new_match - 1]
if str2[new_match] == c:
new_match += 1
valid = True
for i in range(n):
window_end = pos - i
if 0 <= window_end < m:
if str1[i] == 'T' and window_end == m - 1:
valid &= (new_match == m)
elif str1[i] == 'F' and window_end == m - 1:
valid &= (new_match != m)
if valid and canGenerate(pos + 1, new_match):
result.append(c)
match_len = new_match
break
return ''.join(result)
public class Solution {
public string GenerateString(string str1, string str2) {
int n = str1.Length, m = str2.Length;
// KMP failure function
int[] lps = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && str2[i] != str2[j]) j = lps[j - 1];
if (str2[i] == str2[j]) j++;
lps[i] = j;
}
// Check if solution exists
var memo = new Dictionary<(int, int), bool>();
bool CanGenerate(int pos, int matchLen) {
if (pos == n + m - 1) return true;
if (memo.ContainsKey((pos, matchLen))) return memo[(pos, matchLen)];
for (char c = 'a'; c <= 'z'; c++) {
int newMatch = matchLen;
while (newMatch > 0 && str2[newMatch] != c) {
newMatch = lps[newMatch - 1];
}
if (str2[newMatch] == c) newMatch++;
bool valid = true;
for (int i = 0; i < n; i++) {
int windowEnd = pos - i;
if (windowEnd >= 0 && windowEnd < m) {
if (str1[i] == 'T' && windowEnd == m - 1) {
valid &= (newMatch == m);
} else if (str1[i] == 'F' && windowEnd == m - 1) {
valid &= (newMatch != m);
}
}
}
if (valid && CanGenerate(pos + 1, newMatch)) {
memo[(pos, matchLen)] = true;
return true;
}
}
memo[(pos, matchLen)] = false;
return false;
}
if (!CanGenerate(0, 0)) return "";
var result = new char[n + m - 1];
int currentMatch = 0;
for (int pos = 0; pos < n + m - 1; pos++) {
for (char c = 'a'; c <= 'z'; c++) {
int newMatch = currentMatch;
while (newMatch > 0 && str2[newMatch] != c) {
newMatch = lps[newMatch - 1];
}
if (str2[newMatch] == c) newMatch++;
bool valid = true;
for (int i = 0; i < n; i++) {
int windowEnd = pos - i;
if (windowEnd >= 0 && windowEnd < m) {
if (str1[i] == 'T' && windowEnd == m - 1) {
valid &= (newMatch == m);
} else if (str1[i] == 'F' && windowEnd == m - 1) {
valid &= (newMatch != m);
}
}
}
if (valid && CanGenerate(pos + 1, newMatch)) {
result[pos] = c;
currentMatch = newMatch;
break;
}
}
}
return new string(result);
}
}
/**
* @param {string} str1
* @param {string} str2
* @return {string}
*/
var generateString = function(str1, str2) {
const n = str1.length, m = str2.length;
// KMP failure function
const lps = new Array(m).fill(0);
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && str2[i] !== str2[j]) j = lps[j - 1];
if (str2[i]
复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | O(26 × (n + m) × m × n) |
| 空间复杂度 | O((n + m) × m) |
其中 n 是 str1 的长度，m 是 str2 的长度。时间复杂度包括：
- 对每个位置(n+m-1个)尝试26个字符
- 每次尝试需要检查所有约束条件(最多n个)
- KMP匹配更新需要O(m)时间 空间复杂度主要用于动态规划的记忆化存储。