1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
using System.Collections.Generic;
using System.Linq;
void Main()
{
List<string> blocks =
new List<string>() { "bo", "xk", "dq", "cp", "na", "gt", "re", "tg", "qd", "fs",
"jw", "hu", "vi", "an", "ob", "er", "fs", "ly", "pc", "zm" };
List<string> words = new List<string>() {
"A", "BARK", "BOOK", "TREAT", "COMMON", "SQUAD", "CONFUSE"};
var solver = new ABC(blocks);
foreach( var word in words)
{
Console.WriteLine("{0} :{1}", word, solver.CanMake(word));
}
}
class ABC
{
readonly Dictionary<char, List<int>> _blockDict = new Dictionary<char, List<int>>();
bool[] _used;
int _nextBlock;
readonly List<string> _blocks;
private void AddBlockChar(char c)
{
if (!_blockDict.ContainsKey(c))
{
_blockDict[c] = new List<int>();
}
_blockDict[c].Add(_nextBlock);
}
private void AddBlock(string block)
{
AddBlockChar(block[0]);
AddBlockChar(block[1]);
_nextBlock++;
}
public ABC(List<string> blocks)
{
_blocks = blocks;
foreach (var block in blocks)
{
AddBlock(block);
}
}
public bool CanMake(string word)
{
word = word.ToLower();
if (word.Length > _blockDict.Count)
{
return false;
}
_used = new bool[_blocks.Count];
return TryMake(word);
}
public bool TryMake(string word)
{
if (word == string.Empty)
{
return true;
}
var blocks = _blockDict[word[0]].Where(b => !_used[b]);
foreach (var block in blocks)
{
_used[block] = true;
if (TryMake(word.Substring(1)))
{
return true;
}
_used[block] = false;
}
return false;
}
}
|
