程式隨筆
0%

【LeetCode】Count The Repetitions

Posted on Edited on In Disqus:

#題目

Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] =”abcabcabc”.

On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.

You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.

Example:

Input:
s1=”acb”, n1=4
s2=”ab”, n2=2

Return:
2

#解題

如何判定S2會包含在S1的倍數之中，我採取的方法是將遍歷S1的每個字元，每當該字元與S2相同時，S2的指標往前一格。

[a]cb
S1 : a
[a]b
S2 : a

a[c]b
S1 : c
a[b]
S2 : b

ac[b]
S1 : b
a[b]
S2 : b

[a]cb
S1 : a
[a]b
S2 : a

以下省略….

直到S1 * N1的字元次數被跑完時，可以知道S2被重複了幾次，這時候將重複次數除以N2即為真正可重複的次數

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[TestMethod()]
public void GetMaxRepetitionsTest()
{
    //arrange
    var s1 = "acb";
    var n1 = 4;
    var s2 = "ab";
    var n2 = 2;
    var sut = new Solution();

    var expected = 2;

    //act
    var actual = sut.GetMaxRepetitions(s1, n1, s2, n2);
    
    //assert
    actual.Should().Be(expected);
}
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
public int GetMaxRepetitions(string s1, int n1, string s2, int n2)
{
    var SlChars = s1.ToCharArray();
    var S2Chars = s2.ToCharArray();

    int Repetitions = 0;
    int Cursor = 0;

    for (int i = 0; i < SlChars.Length * n1 ; i++)
    {
        if (SlChars[i % SlChars.Length] == S2Chars[Cursor])
        {
            Cursor++; 
        }

        if (Cursor == S2Chars.Length)
        {
            Repetitions++;
            Cursor = 0;
        }
    }


    return Repetitions / n2;
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[TestMethod()]
public void GetMaxRepetitionsTest_2()
{
    //arrange
    var s1 = "ab";
    var n1 = 3;
    var s2 = "ab";
    var n2 = 4;
    var sut = new Solution();

    var expected = 0;

    //act
    var actual = sut.GetMaxRepetitions(s1, n1, s2, n2);

    //assert
    actual.Should().Be(expected);
}

單元測試直接通過

#解析

LeetCode回傳Time Limit Exceeded，表示這效率不能接受，所以來試試看優化它

優化

想先把迴圈內計算餘數的地方拿掉，這個地方應該卡掉一堆效能

1
if (SlChars[i % SlChars.Length] == S2Chars[Cursor])

改寫之後不再迴圈內計算餘數，讓每個變數的操作都盡量簡單化

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
public int GetMaxRepetitions(string s1, int n1, string s2, int n2)
{
    var SlChars = s1.ToCharArray();
    var S2Chars = s2.ToCharArray();

    int Repetitions = 0;

    int S1Cursor = 0;
    int S2Cursor = 0;


    int Count = 0;
    while (Count < n1)
    {
        if (SlChars[S1Cursor] == S2Chars[S2Cursor])
        {
            S2Cursor++;
        }

        S1Cursor++;

        if (S2Cursor == S2Chars.Length)
        {
            Repetitions++;
            S2Cursor = 0;
        }

        if (S1Cursor == SlChars.Length)
        {
            S1Cursor = 0;
            Count++;
        }

    }

    return Repetitions / n2;
}

結果LeetCode還是判定逾時,果然事情不是憨人我想的那麼簡單，暴力破解法行不通

/images/20180611/3.jpg

尋找Loop Pattern

在這邊決定改變作法，首先如果S1會重複表示有可能發生重複狀況的發生，例如

S1 = aabaabaab
n1 = 3

S2 = aba
n2 = 1

0 4 7 1 4 7
a a b a a b a a b a a b a a b a a b a …..
a b a a b a a b a a b a a b a a b a …..

*第一列表示S2字首a比對到時，相對於各組S1的Index

*第二列 S1的排序組

*第三列 S2比對相符組

可以發現第一次重複的Index為4，所以繼續往下排就會一直重複的狀況發生，也藉著這個特性可以找出一個算法。

  • 第二次4在整個S1的排列組裡面Index為13，第一次4在整個排列組裡面Index也是4
  • 兩者之間總共可以包含3組S2
  • 所以之後只要每加9個字元，就會多出3組S2

依照此特性修改程式

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
public int GetMaxRepetitions(string s1, int n1, string s2, int n2)
{
    var S1Chars = s1.ToCharArray();
    var S2Chars = s2.ToCharArray();


    int S2Cursor = 0;
    int Repetitions = 0;
    var LogFirstLetterMatchInS1Index = new Dictionary<int, Tuple<int, int>>();
    for (int i = 0; i < S1Chars.Length * n1 ; i++)
    {
        var S1Index = i % s1.Length;
        if (S1Chars[S1Index] == S2Chars[S2Cursor])
        {
            if (S2Cursor == 0)
            {
                if (LogFirstLetterMatchInS1Index.ContainsKey(S1Index))
                {
                    //形成Loop了
                    var PreSameIndexValue = LogFirstLetterMatchInS1Index[S1Index];

                    //Repetitions
                    var OneLoopS2Count = (Repetitions - PreSameIndexValue.Item2);

                    var OneLoopDistance = i - PreSameIndexValue.Item1;

                    while ((i + OneLoopDistance) < S1Chars.Length * n1)
                    {
                        Repetitions += OneLoopS2Count;

                        i += OneLoopDistance;
                    }

                }
                else
                {
                    LogFirstLetterMatchInS1Index.Add(S1Index,new Tuple<int, int>(i, Repetitions));
                }
            }
            S2Cursor++;
        }

        if (S2Cursor == S2Chars.Length)
        {
            Repetitions++;

            S2Cursor = 0;
        }
    }

    return Repetitions / n2;
}

雖然終於通過LeetCode測驗，但成績依然不是很理想，不過一些大神的解法目前還沒完全了解，所以先用這個算法勉強過關，之後有懂更佳的方式再繼續優化。

這題寫了兩天且數次拿著計算紙在床上睡著後終於勉強想通，不愧是Hard等級的題目阿