Question

Two words or phrases in English are anagrams if their letters (and only their letters), rearranged, are the same. We assume that upper and lower case are indistinguishable, and punctuation and spaces don't count. Two phrases are anagrams if they contain exactly the same number of exactly the same letters, e.g., 3 A's, 0 B's, 2 C's, and so forth.

Some examples and non-examples of regular anagrams:

* The eyes / they see (yes)
* moo / mo (no)
* Clint Eastwood / Old west Action! (yes)
* Dormitory / Dirty Room (yes)
* Debit card / bad credit (yes)
* One good turn deserves another / Do rogues endorse that? No! Never! (yes)

When are two phrases anagrams? Your job for this assignment is to solve a slight variant of the traditional anagram problem, called the wild anagram problem.

Suppose you have two phrases, which we'll call left, and right. Unlike traditional anagram phrase pairs - the eyes / they see - with a wild anagram pair, the second string, the one on the right, can contain the wild card symbol *, which can stand for any letter. Thus

the eyes / th*y *ee

is a wild pair, with one * standing for e and the other * standing for s

Here are some more examples, with explanations

abc / *** (true: one * for each letter)
The eyes / they see (true - don't have to be *s)
ab / *** (false - *'s MUST stand for something, so right string is too big.
ab / * (false)
xxy / *x* (true - one * for x, one for y)
xxy / y** (true - both *'s for x)
Clint Eastw**d / Old west Action! (false - The symbol *, when it's on the left, is simply ignored - it's just like a comma or period. So there are too many letters on the right.)


Example of a program run:

Enter a phrase:
> Clint Eastwood 
Enter another phrase:
>Old w*st Acti*n! 
true

PROJECT REQUIREMENTS:

1. Your classes must be called WildTester, and WildGram.
2. 
   
3. Your WildTester class must prompt the user to enter each phrase separately. It must use the same Scanner object to read in each of the two input phrases.
4. 
   
5. Your program must print true if the wild anagram relationship is satisfied, and false if it isn't. All console input and output must be done by the WildTester class.
6. 
   
7. Your WildGram class must have an isWildGram method, which takes two String parameters - the left and right phrases to be tested, and returns a boolean value. The boolean value returned should be true if the wild anagram relationship is satisfied, and false, if it isn't.
8. 
   
9. Your WildTester class must create an instance of the WildGram class and call the WildGram method isWildGram to determine if the input satisfies the wild anagram relationship.
10. 
    
11. You MUST use one or more array(s) in an essential way in your solution to this project.
12. 
    
13. You may NOT import and use the ArrayList class for this project. (An array is not the same thing as an ArrayList.)
14. Important: for this project upper and lower case are indistinguishable, so after reading the strings, convert them to lower case. Also, remember that except for the * symbol, all punctuation, other symbols, and spaces are ignored.
15. 
    
16. 
    

Some tips:

1. 
   
2. Remember to use the nextLine Scanner method, rather than next, since spaces may be present in the two phrases that are submitted.
3. Use the String methods toLowerCase and, possibly, toCharArray, which converts a string into an array of chars. (Consult the Java API).
4. For some useful background on characters and how to work with them, watch the movies in the textbook at the ends of sections 4.1 and 7.1.
5. Very important: Work out what's going on with pencil and paper first.

Some algorithms you might try on this problem



Algorithm Idea #1: convert strings to arrays of chars using the string method toCharArray. March down the first array (representing the left string). When you encounter a letter, look for it in the second array. If you find it, blank out the occurrence in the second array; if you don't find it, look in the second array for a * to match with the left-side letter. If you find one, blank that * out; if you don't find one, then the strings aren't a wild anagram pair. When you're all done, you've got a wild anagram if your searches in the right array never goes bad, and if, at the end, there are no letters and no *'s in the second array. Make sense? Do the algorithm with pencil and paper on this pair:

abac / *a*b.

Algorithm Idea #2: make a scoreboard array for the letters a to z. Move across the left string, and every time you encounter a letter, up its count by 1. When you're done you have a complete inventory, of all the letters in the left string: 3 a's, 0 b's, 2 c's, and so forth. Then, move across the right string. Every time you encounter a letter, lower its count on the scoreboard by one. At the same time, count the number of *'s you discover as you traverse the string.

You've found a true wild anagram after traversing left and right strings if 1) the scoreboard ends up with all entries >= 0; and 2) if you add up the final scoreboard entries, which is the number of left string characters that don't have mates in the right string, then that number should equal the count of the *'s in the right string. Once again do the algorithm with pencil and paper for the pair above (notice that for your paper version of the example above you only need three cells in your array, and not twenty-six, since the strings only involve a, b and c.)

IMPORTANT NOTE: Do NOT put import statements in your classes.

import java.util.Scanner;

Place your WildGram class here.

Answer 1

class WildGram
{
   //implemention of 1st Algorithm
   public boolean isWildGram(String left, String right)
   {
       //System.out.println("\nLeft: "+left + "\tRight: "+right);
       //get left string length and right one length
       int lenLeft = left.length();
       int lenRight = right.length();
       //convert both strings to char Array
       char []lefts = left.toLowerCase().toCharArray();
       char []rights = right.toLowerCase().toCharArray();
       //variable to store letter in left array
       char find;
       //index of above char in right array
       int ind;
       //for each char in left
       for(int i = 0;i<lenLeft;i++)
       {
           //if it is letter
           if(Character.isLetter(lefts[i]))
           {
               //copy left i_th letter to find
               find = lefts[i];
               //find the char in right one
               ind = findChar(rights,find);
               //if found
               if(ind != -1)
               {
                   //set it's index to 0 , means block out
                   rights[ind] = 0;
               }
               //if not found
               else
               {
                   //find * and block out that index
                   //if not return false.it's not a wildgram
                   ind = findChar(rights,'*');
                   if(ind == -1)
                   {
                      
                       return false;
                   }
                   else
                   {
                       rights[ind] = 0;
                   }
               }
           }
       }
       //if above steps are done.
       //check for any extra letters remained in right array
       for(int i = 0;i<lenRight;i++)
       {
           //if it is a letter or * wild card return false.
           if(Character.isLetter(rights[i]) || rights[i] == '*')
           {
               return false;
           }
       }
       //finaly nowhere return false executed.
       //then return true
       return true;
   }
   //function that returns given char in a array of chars
   //if not returns -1
   public int findChar(char[] chars,char find)
   {
       for(int i = 0;i<chars.length;i++)
       {
           if(chars[i] != 0 && chars[i] == find)
           {
               return i;
           }
       }
       return -1;
   }
}
import java.util.Scanner;
class WildTester
{
   public static void main(String args[])
   {
      
       /*
       System.out.println("Result: "+test.isWildGram("the eyes","th*y *ee"));
       System.out.println("Result: "+test.isWildGram("abc","***"));
       System.out.println("Result: "+test.isWildGram("The eyes","they see"));
       System.out.println("Result: "+test.isWildGram("ab","***"));
       System.out.println("Result: "+test.isWildGram("xxy","*x*"));
       System.out.println("Result: "+test.isWildGram("xxy","y**"));
       System.out.println("Result: "+test.isWildGram("ab","*"));
       System.out.println("Result: "+test.isWildGram("Clint Eastw**d","Old west Action!"));
       */
       Scanner in = new Scanner(System.in);
       System.out.println("Enter a Phrase: ");
       String left = in.nextLine();
       System.out.println("Enter another Phrase: ");
       String right = in.nextLine();
       //create object of WIldGram and call isWildGram() function
       WildGram test = new WildGram();
       System.out.println(test.isWildGram(left,right));
      
   }
}

C\Windows\SYSTEM32\cmd.exe Enter a Phrase Clint Eastvood Enter another Phrase: 0ld wst Actixn! true Kprogram exited with code: 0) Press any key to continue