1178. 猜字谜
Code A:9/10 TLE
public class Solution {
public IList<int> FindNumOfValidWords(string[] words, string[] puzzles)
{
var ret = new int[puzzles.Length];
var first = new Dictionary<char, Dictionary<int, int>>();
for (var ch = 'a'; ch <= 'z'; ch++)
first[ch] = new Dictionary<int, int>();
for (var i = 0; i < puzzles.Length; i++)
first[puzzles[i][0]][Word2Int(puzzles[i])] = i;
foreach (var word in words)
{
var value = Word2Int(word);
for (var ch = 'a'; ch <= 'z'; ch++)
{
if(ContainChar(value, ch))
foreach(var (k,v) in first[ch])
if(Rule2(value, k))
ret[v]++;
}
}
return ret;
}
public static int Word2Int(string str)
{
var ret = 0;
foreach (var ch in str)
ret |= 1 << (ch - 'a');
return ret;
}
public static bool Rule2(int word, int puzzles) => (word & ~puzzles) == 0;
public static bool ContainChar(int value, char ch) => (value & (1 << (ch - 'a'))) > 0;
}
依据官方的题解,写的Code B:
using hash = System.Int32;
using flag = System.Int32;
public class Solution
{
const int PUZZLE_LENGTH = 7;
public IList<int> FindNumOfValidWords(string[] words, string[] puzzles)
{
var ret = new int[puzzles.Length];
var map = new Dictionary<hash, int>();
foreach (var word in words) // 这里还可以把总1比特数大于7的剔除掉,不过不剔除也能双百就是了
{
var hash = word.ToHash();
if (!map.ContainsKey(hash))
map[hash] = 0;
map[hash]++;
}
for (var i = 0; i < puzzles.Length; i++)
{
var puzzle = puzzles[i];
for (var j = 0; j < (1 << (PUZZLE_LENGTH - 1)); j++)
{
var num = puzzle[0].ToFlag();
for (var k = 0; k < (PUZZLE_LENGTH - 1); k++)
if (((j >> k) & 1) > 0)
num |= puzzle[k + 1].ToFlag();
ret[i] += map.GetValueOrDefault(num, 0);
}
}
return ret;
}
}
public static class Extension
{
public static hash ToHash(this string str)
{
var ret = 0;
foreach (var ch in str)
ret |= 1 << (ch - 'a');
return ret;
}
public static flag ToFlag(this char ch) => 1 << (ch - 'a');
}