首页 > 代码库 > LeetCode:Ransom Note_383
LeetCode:Ransom Note_383
LeetCode:Ransom Note
【问题再现】
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") -> falsecanConstruct("aa", "ab") -> falsecanConstruct("aa", "aab") -> true【优质算法】
public class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] arr = new int[26]; for (int i = 0; i < magazine.length(); i++) { arr[magazine.charAt(i) - ‘a‘]++; } for (int i = 0; i < ransomNote.length(); i++) { if(--arr[ransomNote.charAt(i)-‘a‘] < 0) { return false; } } return true; }}
【题后反思】
本题用到了统计字符出现频率的数组计数器，这种实现最为简单，不做解释。
我做这道题的时候考虑了magazine要按照Ransom的顺序，结果一直通不过，把问题想的复杂化了。
public static boolean canConstruct(String ransomNote, String magazine) { int Sp = 0; int Lp = 0; int count = 0; while (Lp < magazine.length()) { if(Sp==ransomNote.length()) break; if (ransomNote.charAt(Sp)==magazine.charAt(Lp)) { count++; System.out.print(ransomNote.charAt(Sp)); Sp++; Lp++; } else Lp++; } if (count == ransomNote.length()) return true; else return false;
这种题目也可以利用HashMap来计算：
public static boolean canConstruct(String ransomNote, String magazine) { HashMap<Character,Integer> myMap = new HashMap<>(); for(int i=0;i<magazine.length();i++) { if(myMap.containsKey(magazine.charAt(i))) myMap.put(magazine.charAt(i),myMap.get(magazine.charAt(i))+1); else myMap.put(magazine.charAt(i),1); } for(int i=0;i<ransomNote.length();i++) { if(myMap.containsKey(ransomNote.charAt(i))) { myMap.put(ransomNote.charAt(i),myMap.get(ransomNote.charAt(i))-1); if(myMap.get(ransomNote.charAt(i))<=0) return false; } else return false; } return true; }
LeetCode:Ransom Note_383
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。