[力扣] 算法 1178 (C#)

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');
}

发表评论