Given an arbitrary ransom note, consisting of 15 20 words and several magazines,

Question

Given an arbitrary ransom note, consisting of 15 20 words and several magazines, write a function that will return a true, if the ransom note can be constructed from the words in the magazines, otherwise it will return a false. Each word in the magazines can only be used once in your ransom note. The algorithm should work efficiently, such as, utilizing hash tables for storing and looking up strings. An example hash function maybe the sum of the ascii values of all the characters in the string, modulus an appropriate positive integer. Utilize the built in string class, and some of its methods. For testing the code, utilize the ransom note and the magazines provided on the Blackboard in files RansomNote.dat, Magazine1.dat, Magazine2.dat, Magazine3.dat, Magazine4.dat, Magazine5.datand Magazine6.dat

Explanation / Answer

}

public class RansomNote { public static void main(String[] args) { if(args.length < 2) { System.out.println("You need to enter a ransom note and the " + "contents of the magazines both in quotes."); System.exit(1); } String note = args[0]; String mag = args[1]; System.out.println("Ransom note: " + note); System.out.println("Magazine contents: " + mag); System.out.println("Can construct ransom note from mag contents?"); System.out.println(ransomNote2(note, mag));

}

public static boolean ransomNote1(String note, String mag) { int[] count = new int[256]; // Assumes only ASCII characters for(int i = 0; i < mag.length(); i++) { int c = mag.charAt(i); count[c]++; } for(int i = 0; i < note.length(); i++) { int c = note.charAt(i); count[c]--; if(count[c] < 0) return false; } return true; } public static boolean ransomNote2(String note, String mag) { int[] count = new int[256]; // Assumes only ASCII characters int n = 0; int m = 0; while(n < note.length()) { int nchar = note.charAt(n); if(count[nchar] > 0) { count[nchar]--; n++; } else { while(m < mag.length() && mag.charAt(m) != nchar) { int mchar = mag.charAt(m); count[mchar]++; m++; } if(m >= mag.length()) return false; n++; m++; } } return true; } }

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.