leetcode383.Ransom Note

发表于 更新于 分类于 ，

题目

1
2
3
4
5
6
7
8
9
10
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.

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

假设有一组字母和一组从杂志中获取的字母，问是否能够用从杂志中获取的字母构成想要的那组字母，要求每个单词只能使用一次。

思路一

使用索引为字母的数组来存储该字母还剩下几个没有从杂志中找到。每从杂志中找到一个字母，对应字母位置上的数字减一，每遇到一个字母则该字母位置上的数字加一。如果没有多余的字母，则说明可以找到足够多的字母拼接。

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
public boolean canConstruct(String ransomNote, String magazine) {
    if(ransomNote.isEmpty()) return true;
    if(ransomNote.length() > magazine.length()) return false;
    int p1 = 0, p2 = 0;
    int[] count = new int[26];
    int wordCount = 0;
    while(p1 < ransomNote.length() && p2 < ransomNote.length()) {
        char c1 = ransomNote.charAt(p1);
        char c2 = magazine.charAt(p2);
        if(++count[c1-'a'] == 1) {
            wordCount++;
        }
        if(--count[c2-'a'] == 0) {
            wordCount--;
        }
	    p1++;
	    p2++;
	}
		
	while(p2 < magazine.length()) {
	    if(wordCount == 0) break;
	    char c = magazine.charAt(p2);
	    count[c-'a']--;
	    if(count[c-'a'] == 0) {
	        wordCount--;
	    }
	    p2++;
	}
	return wordCount == 0;
}

思路二：找不到字母就结束

思路二利用java的API来查找magazine中从上一个找到的字母开始，下一个字母所在的位置。如果找不到，则说明无法完成拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canConstruct(String ransomNote, String magazine) {
    int len=ransomNote.length();
    int[] index = new int[128];
    for(int i = 0; i < len; i++){
        char cu=ransomNote.charAt(i);
        int result=magazine.indexOf(cu,index[cu]);
        if(result == -1){
            return false;
        }
        else{
            index[cu]=result + 1;   
        }   
    }
    return true;
}