leetcode 383. Ransom Note（赎金票据）

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input: ransomNote = “a”, magazine = “b”
Output: false
Example 2:

Input: ransomNote = “aa”, magazine = “ab”
Output: false
Example 3:

Input: ransomNote = “aa”, magazine = “aab”
Output: true

题目是赎金，但是好像和赎金也没啥关系，就是字符串。
ransomNote中的字母要由magazine中的字母组成。
magazine中每个字母只能用一次。

思路：

说白了就是判断ransomNote是不是magazine的子串，即由magazine中的字母组成，不限制顺序。
但是magazine中每个字母只能用一次。

英文小写字母总共就26个，只要统计每个字母出现的次数，
ransomNote中每个字母出现的次数只要小于magazine中对应字母的次数，就为true.

public boolean canConstruct(String ransomNote, String magazine) {
    int nr = ransomNote.length();
    int nm = magazine.length();
    int n = Math.max(nr, nm);
    int[] cntr = new int[26];
    int[] cntm = new int[26];
    
    for(int i = 0; i < n; i ++) {
        if(i < nr) cntr[ransomNote.charAt(i)-'a'] ++;
        if(i < nm) cntm[magazine.charAt(i)-'a'] ++;
    }
    
    for(int i = 0; i < 26; i++) {
        if(cntr[i] > cntm[i]) return false;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

还有一种方法，不统计次数，直接依次查找，找不到就返回false.
由于magazine中每个字母只能用一次，一旦这个字母用过就不能再用，假设这个字母的index为 i,
下次再找这个字母，只能从i + 1开始找。

保存每个字母当前找到的index, 下次从index + 1开始找这个字母。

public boolean canConstruct(String ransomNote, String magazine) {
    int[] startIdx = new int[26];
    
    for(char cur : ransomNote.toCharArray()) {
        int index = magazine.indexOf(cur, startIdx[cur - 'a']);
        if(index == -1) return false;
        startIdx[cur-'a'] = index+1;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10