Im having trouble on an exercise, and dont know where to begin and what stagagy to take. The exercise is to write a program which takes two strings s1 and s2 and checks whether s2 can be made by rearranging some of the characters which occur in s1. For example if s1 is "abc" and s2 is "ca" the program should return "true". If s1 is "abc" and s2 is "bbc" the answer should be "false" because s2 requires two "b"s and "abc" only has one. I have to make the program time efficient, runs below 25 milliseconds. Assume that s1 and s2 are made of the 26 lower case ascii characters a....z. If the following code is executed: (new Scrabble(s1)).scrabble(s2); the return is true if s2 can be built using characters from s1, and false otherwise. Each occurrence of a character can only be used once. For example, (new Scrabble("abc")).scrabble("ba");
returns true and (new Scrabble("bbc")).scrabble("bbb");
returns false.
Im thinking creating an array of 26 int, and incrementing it when s1's letters are read, and dercrementing it when s2 letters are read. if the array has 0's then it matches, if -1, it doesnt! But how do i start this, how do i read the letters and increment the array??
If s2 can be made by rearranging s1, then each character in s2 is a character in s1, and the number of occurrences of each character in s2 is at least as many occurrences as in s1.
/* StringPlay.java * @Author: Charles Bell * @version: Nov 2, 2002 * * Write a program which takes two strings s1 and s2 and checks whether s2 can * be made by rearranging some of the characters which occur in s1. For example * if s1 is "abc" and s2 is "ca" the program should return "true"". */ import java.util.*;
public class StringPlay{
public static void main(String[] args){ StringPlay stringPlay = new StringPlay(); stringPlay.test1();
for (int i = 0; i < 100; i++){ stringPlay.test2(); }
}
public void test1(){ long before = (new Date()).getTime(); System.out.println("Time before: " + String.valueOf(before));
String s1 = "abc"; String s2 = "ca"; //the program should return "true"". if (canRearrange(s1, s2)){ System.out.println(s1 + " can be rearranged to make " + s2); }else{ System.out.println(s1 + " can not be rearranged to make " + s2); } long after = (new Date()).getTime(); System.out.println("Time after: " + String.valueOf(after)); long duration = after - before; System.out.println("This operation took: " + String.valueOf(duration) + " milliseconds."); }
public void test2(){ long before = (new Date()).getTime();
for (int i = 0; i < wordLength; i++){ s1 = s1 + alphabet.charAt((int)(alphabet.length() * Math.random())); } for (int i = 0; i < testWordLength; i++){ s2 = s2 + alphabet.charAt((int)(alphabet.length() * Math.random())); } if (canRearrange(s1, s2)){ System.out.println(s1 + " can be rearranged to make " + s2); }else{ System.out.println(s1 + " can not be rearranged to make " + s2); } long after = (new Date()).getTime(); System.out.println("Time after: " + String.valueOf(after)); long duration = after - before; System.out.println("This operation took: " + String.valueOf(duration) + " milliseconds."); }
/** If s1 can be rearranged to make s2, then all the characters in s2 must be in s1. * Thus must simply iterate to check to verify. No rearrangement is required. */ public boolean canRearrange(String s1, String s2){ boolean status = true; for (int i = 0 ; i < s2.length(); i++){ status = status && (s1.indexOf(s2.charAt(i)) >= 0); status = status && (occurences(s1, s2.charAt(i)) >= occurences(s2, s2.charAt(i))); } return status; }
public int occurences(String s, char c){ int n = 0; char[] characters = s.toCharArray(); for (int i = 0; i < characters.length; i++){ if (characters[i] == c) n++; } return n; }
Previous Topic
