[C#][LeetCode][Easy] 383. Ransom Note

心得

這題要比對字串變數ransomNote是否存在於字串變數magazine裡。

問題

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom

note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:

You may assume that both strings contain only lowercase letters.

1
2
3
4
5
6
7
8

canConstruct("a", "b") -> false
>
> canConstruct("aa", "ab") -> false
>
> canConstruct("aa", "aab") -> true
>
>

答案

  1. 先將所有字母的數量統計在比較
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

public class Solution {
public bool CanConstruct(string ransomNote, string magazine) {
if (ransomNote.Length > magazine.Length)
{
return false;
}

Dictionary<char, int> dty_1 = getCharCount(ransomNote);
Dictionary<char, int> dty_2 = getCharCount(magazine);

foreach (var item in dty_1)
{
int tmp = 0;
if (!dty_2.TryGetValue(item.Key, out tmp) || item.Value > tmp)
{
return false;
}
}

return true;
}

private Dictionary<char, int> getCharCount(string str)
{
Dictionary<char, int> dty = new Dictionary<char, int>();

while (str.Length > 0)
{
dty.Add(str[0], str.Count(x => x == str[0]));
str = str.Replace(str[0].ToString(), "");
}

return dty;
}
}
  1. 方法1的簡化版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class Solution {
public bool CanConstruct(string ransomNote, string magazine) {
if (ransomNote.Length > magazine.Length)
{
return false;
}

while (ransomNote.Length > 0)
{
if (ransomNote.Count(x => x == ransomNote[0]) > magazine.Count(x => x == ransomNote[0]))
{
return false;
}

ransomNote = ransomNote.Replace(ransomNote[0].ToString(), "");
}

return true;
}
}
  1. 這方法是在解答內看到的,解題思路與方法1差不多但是速度快了很多。
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 class Solution {
public bool CanConstruct(string ransomNote, string magazine) {
if (ransomNote.Length > magazine.Length)
{
return false;
}

int[] table = new int[26];
foreach (var item in magazine)
{
table[item - 'a']++;
}
foreach (var item in ransomNote)
{
table[item - 'a']--;
if (table[item - 'a'] < 0)
{
return false;
}
}

return true;
}
}