-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
52 lines (50 loc) · 1.58 KB
/
Program.cs
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
using System;
using System.Collections.Generic;
namespace StampingTheSequence
{
class Program
{
static void Main(string[] args)
{
string stamp = "abc", target = "bbbbb";
Console.WriteLine(MovesToStamp(stamp, target));
}
public static int[] MovesToStamp(string stamp, string target)
{
var res = new List<int>();
var checkedIndexes = new HashSet<int>();
var canStamp = true;
while (canStamp)
{
var temp = false;
for (int i = 0; i <= target.Length - stamp.Length; i++)
{
if (!IsSame(stamp, target, i, checkedIndexes)) continue;
temp = true;
res.Add(i);
for (int j = 0; j < stamp.Length; j++)
checkedIndexes.Add(i + j);
}
canStamp = temp;
}
if (checkedIndexes.Count != target.Length) return new int[0];
res.Reverse();
return res.ToArray();
}
public static bool IsSame(string stamp, string target, int li, HashSet<int> checkedIndexes)
{
int count = 0;
for (int i = 0; i < stamp.Length; i++)
{
if (checkedIndexes.Contains(li + i))
{
count++;
continue;
}
if (stamp[i] != target[li + i])
return false;
}
return count < stamp.Length;
}
}
}