Tom's Guide | Tom's Hardware | Tom's Games
 |
 |
 |
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.
Thanks in advance!
Here's one way:
Make an array of 26 character counts. Initialize it to zeros.
Run through s1 and increment the character count for each letter in the string.
Run through s2 and decrement the character count for each letter in the string. If any count goes negative, you lose. If you get to the end of the string, and all the counts are still at least 0, you win.
0 
thats the stragegy i was thinking off, but do u think it is an efficient one? and how do i increment the array if lets say the first letter "a" is inputted, then "b" is inputting how do i increment at index 1 of the array! would you be able to help me start the program?? that will be very much appraciated, thanks!!
Rams
0
> thats the stragegy i was thinking off, but do u think it is an efficient one?
Actually, you'd be hard pressed to find a more efficient method. You could sort both strings, but that would take longer and be harder.
I'll show you how to do it in C, and you translate it to Java.
int Scrabble(char *s1, char *s2)
{
int CharCounts[26] = {0};
int StringLength;
int i;StringLength = strlen(s1);
for (i = 0; i < StringLength; ++i)
++CharCounts[s1[i] - 'a'];StringLength = strlen(s2);
for (i = 0; i < StringLength; ++i)
if (CharCounts[s2[i] - 'a'] == 0)
return(false);
else
--CharCounts[s1[i] - 'a'];
return(true);
}
0
I no good in java but im terrible in C, would anybody be able to translate this for me from C to JAVA.
int Scrabble(char *s1, char *s2)
{
int CharCounts[26] = {0};
int StringLength;
int i;StringLength = strlen(s1);
for (i = 0; i < StringLength; ++i)
++CharCounts[s1[i] - 'a'];StringLength = strlen(s2);
for (i = 0; i < StringLength; ++i)
if (CharCounts[s2[i] - 'a'] == 0)
return(false);
else
--CharCounts[s1[i] - 'a'];
return(true);
}
Thanks in advance
0
I won't take away all the fun by doing it all, but I'll give you some tips:
char * in C should generally translate to String in Java.
instead of strlen (astring), Java uses astring.length(); (or maybe without the parenthesis.)
This should be enough to get you to translate. Good luck,
SN
0
i get teh char*C and strlen already, but i dont understand this 2 statements:
int CharCounts[26] = {0};
is this just initialising the counter at0, but wot is the 26 for,i'm persuming it is the size of the array?? if so how do u do this in java??CharCounts[s2[i] - 'a'] == 0
i get this bit "CharCounts[s2[i]" but not this " -'a' ". help???
0
if (CharCounts[s2[i] - 'a'] == 0)
It's the way of translating your subscripts. CharCounts[] is an array of integers, and the array has 26 members, but the array subscripts go from 0 to 25. s2[] is an array of characters, and the contents are characters from 'a' to 'z'. If you subtract 'a' from each character, and cast it to an integer, you get a number from 0 to 25, and that's what you need to index into the CharCounts array.
Maybe we should have used an intermediate variable for the index.
int TempIndex;
for (i = 0; i < StringLength; ++i)
{
TempIndex = (int) s1[i];
TempIndex -= (int) 'a';
++CharCounts[TempIndex];
}By the way, there better not be any spaces in either string, or this program could fail miserably. There is no error checking.
There was an error in the original code. The s1 in the decrement line should have been s2.
0
so does that mean ur having 3 arrays, one for CharCount which takes intagers, one for s1 which takes the characters of first string and one for s2 which takes the characters for second string? I dont get this thing about subtracting 'a', and casting onto an intager, would u be able to explain in more detail? Thanks Jim for all your help!
Much appriaciated!
0
In C, a string IS an array of characters. That's how you access each letter of the string. You simply use a subscript.
The CharCount[] array is a count of each letter.
CharCount[0] = number of a's
CharCount[1] = number of b's
CharCount[2] = number of c's
...
CharCount[25] = number of z'sSo you take each letter in s1, and then you have to convert it to an array index.
'a' has to become 0
'b' has to become 1
'c' has to become 2
...
'z' has to become 25Well, in C, you can't really use letters as array subscripts. It does an automatic typecast of the char to an int. Or you can typecast it explicitly. What that really does is take the ascii value of the letter.
'a' becomes 97
'b' becomes 98
'c' becomes 99
...
'z' becomes 122That isn't quite what we want, so we just subtract 97 ('a') from each index. Which gives us the correct number.
0  |
 |
 |
This post is quite old and has been locked from receiving new replies. Please create a new posting instead.
| Ads by Google |
