深圳航空公司官方网站,凉山州建设网站,cms公司中国,企业网站建立的流程文章目录 一、题目二、C# 题解 一、题目 你有两个字符串#xff0c;即 pattern 和 value。 pattern 字符串由字母 a 和 b 组成#xff0c;用于描述字符串中的模式。例如#xff0c;字符串 catcatgocatgo 匹配模式 aabab即 pattern 和 value。 pattern 字符串由字母 a 和 b 组成用于描述字符串中的模式。例如字符串 catcatgocatgo 匹配模式 aabab其中 cat 是 ago 是 b该字符串也匹配像 a、ab 和 b 这样的模式。但需注意 a 和 b 不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
示例 1 输入 pattern “abba”, value “dogcatcatdog” 输出 true 示例 2 输入 pattern “abba”, value “dogcatcatfish” 输出 false 示例 3 输入 pattern “aaaa”, value “dogcatcatdog” 输出 false 示例 4 输入 pattern “abba”, value “dogdogdogdog” 输出 true 解释 “a”“dogdog”,b“”反之也符合规则 提示
1 len(pattern) 10000 len(value) 1000你可以假设 pattern 只包含字母 a 和 bvalue 仅包含小写字母。 点击此处跳转题目。
二、C# 题解 判断长度是否满足要求。 即判断是否存在一对 (aStr, bStr)使得 aLen * aNum bLen * bNum value.Length。其中 aStr / bStr 分别为 a / b 匹配的字符串。aLen / bLen 分别为 aStr / bStr 的长度。aNum / bNum 分别为 pattern 中 a / b 的个数。 对于所有的有序对 (aStr, bStr)顺序取 pattern 中的每个字符判断 value 对应位置是否匹配。 代码中用 lens 存储所有的有序对 (aStr, bStr)。
public class Solution {public bool PatternMatching(string pattern, string value) {int n pattern.Length, l value.Length; // pattern 长度int aNum pattern.Sum(a a a ? 1 : 0); // pattern 中 a 的个数int bNum n - aNum; // pattern 中 b 的个数Listint[] lens new Listint[](); // lens[i][0]/lens[i][1] 分别为 a/b 匹配的字符串长度if (aNum 0) {if (l % bNum ! 0) return false;lens.Add(new[] { 0, l / bNum });}else if (bNum 0) {if (l % aNum ! 0) return false;lens.Add(new[] { l / aNum, 0 });}elsefor (int i 0; i l / aNum; i)if ((l - i * aNum) % bNum 0)lens.Add(new[] { i, (l - i * aNum) / bNum });foreach (var len in lens) { // 每种 a/b 对应的长度都试一遍bool ans true; // 记录该种长度下是否匹配成功string?[] abStr { null, null }; // 记录 a/b 对应匹配的字符串int index 0; // 当前 value 中的匹配位置for (int j 0; j pattern.Length; j) {int ab pattern[j] - a; // 1 表示 a2 表示 bint abLen len[ab]; // 取出 a_b 对应的匹配字符串长度string sub value.Substring(index, abLen); // 查看 value 中的字符串index abLen; // 更新位置if (abStr[ab] null) { // 之前未出现则用 abStr 记录下来if (abStr[1 - ab] sub) return false; // 如果和另一个字符匹配的字符串一样则返回 falseabStr[ab] sub;}else if (abStr[ab] ! sub) { // 匹配失败ans false; // 该情况返回 falsebreak;}}if (ans) return true; // 如果该情况匹配成功直接返回 true}return false;}
}时间68 ms击败 66.67% 使用 C# 的用户内存36.72 MB击败 33.33% 使用 C# 的用户 优化掉 lens 后可以提升效率
public class Solution {public bool PatternMatching(string pattern, string value) {int n pattern.Length, l value.Length; // pattern 长度int aNum pattern.Sum(a a a ? 1 : 0); // pattern 中 a 的个数int bNum n - aNum; // pattern 中 b 的个数if (aNum 0) return Repeat(value, bNum);if (bNum 0) return Repeat(value, aNum);for (int aLen 0; aLen l / aNum; aLen) {if ((l - aLen * aNum) % bNum ! 0) continue;int bLen (l - aLen * aNum) / bNum;string?[] abStr { null, null };int index 0;bool ans true;for (var i 0; i pattern.Length; i) {int ab pattern[i] - a;int abLen ab 0 ? aLen : bLen;string sub value.Substring(index, abLen);index abLen;if (abStr[ab] null) { if (abStr[1 - ab] sub) return false; abStr[ab] sub;}else if (abStr[ab] ! sub) { ans false; break;}}if (ans) return true;}return false;}// 判断 value 是否重复 n 次public bool Repeat(string value, int n) {if (value.Length % n ! 0) return false;int l value.Length / n;for (int i 0; i l; i)for (int j 1; j n; j)if (value[(j - 1) * l i] ! value[j * l i])return false;return true;}
}时间60 ms击败 100.00% 使用 C# 的用户内存36.51 MB击败 66.67% 使用 C# 的用户
