Problem Set 6 FAQ

Problem 6

1. When I run one of the recursive methods that I’ve written for problem 6, I get a NullPointerException. Do you have any idea of why that might be happening?

   A NullPointerException occurs when you try to call a method using a reference variable with a value of null. For example, if you have a variable named str with a value of null and you call str.length(), you will get this exception because there is no object on which the length() method can be invoked. You may need to check first if the value of a reference variable is null before attempting to use it to call a method.

2. In one of my recursive methods for problem 6, I’m getting a StringIndexOutOfBoundsException. What am I doing wrong?

   Don’t forget that the characters in a string have index values that go from 0 to length - 1. The exception means that your code is using an index from outside that range.

3. In one of my recursive methods for problem 6, I’m using the substring method to create a substring that has everything but the first character from the original string. I’m using the expression str.substring(1, str.length() - 1), but I seem to be losing characters at the end of the string as well.

   Don’t forget that the second parameter to the substring method is non-inclusive. So if you want the last character to be included in the substring, your should use the expression str.substring(1, str.length()) – without the “- 1”. Alternatively, you could use the version of substring that only takes a start index: str.substring(1).

4. I’m having trouble figuring out how to structure the recursive case of one of the recursive methods for problem 6. Do you have any hints on how to do this?

   One thing that can help is to consider what should happen for one or more concrete cases – as we did in the example problem that we covered in lecture.

   For example, let’s say that you needed to write a recursive removeVowels method. As with many recursive methods that operate on strings, this method should make recursive calls on ever smaller substrings. For example, let’s say that we wanted to do removeVowels("movies")

   This would lead to the following sequence of method calls:

   removeVowels("movies")
       removeVowels("ovies")
           removeVowels("vies")
               removeVowels("ies")
                   removeVowels("es")
                       removeVowels("s")
                           removeVowels("")
   

   (The last call might not be needed. It depends on which base cases you choose to include.)

   Then, once you have the sequence of method calls, you should think about what each of these separate method calls should return, treating them as if they were independent of each other. For example, what should removeVowels("ies") return – i.e., what string will result if the vowels in "ies" were removed? Based on these return values, you should be able to figure out how a given invocation of the method should use the return value from the recursive call to form its own return value.

5. One of my recursive methods for problem 6 is not working correctly. Do you have any suggestions?

   Try tracing through some concrete examples of cases in which the your method is not returning the correct value. You might want to try adding some temporary printlns to see if that helps you to diagnose the problem. In particular, you could print what the method will return before it actually returns it. That will allow you to see when the wrong value is being returned.

   In addition, if your method returns a value, make sure that you aren’t throwing away the return value of the recursive call. For example, consider this incorrect version of a recursive method that determines if a string is a palindrome – i.e., if it is a word like “radar” that reads the same in either direction:

   public static boolean isPalindrome(String str) {  
       if (str == null || str.equals("")) {  
           return true;  
       }
   
       // recursive call -- the return value is thrown away
       isPalindrome(str.substring(1, str.length() - 1));
   
       char first = str.charAt(0);
       char last = str.charAt(str.length() - 1);
       if (first != last) {
           return false;
       } else {
           return true;
       }
   }
   

   This version of the method makes the correct recursive call – looking at the substring consisting of everything except the first and last characters – but it throws away the value that is returned.

   To avoid losing the return value of the recursive call, we can do one of two things:

   1. assign it to a variable, and then do something with that variable
   2. make the recursive call part of a return statement, if doing so makes sense. It may not always make sense – especially if the value that the current method call should return depends on the value that was returned by the recursive call.

6. I’m having trouble with the recursive trim method. Do you have any suggestions.

   First, it’s worth noting that you will likely need an additional base case beyond our usual one for string inputs.

   Given the description of what the method is supposed to do, for what cases besides the empty string would it be possible to return the correct solution without needing to make a recursive call?

   Second, consider including more than one possible recursive call. The following concrete cases can help in coming up with the different possible calls:

   • If the current call is

     trim("  hello")
     

     what should the recursive call be – i.e., what smaller subproblem would bring me closer to one of my base cases, and would do so in such a way that I could use the solution to the subproblem to determine the solution to the current problem?

   • If the current call is

     trim("hello    ")
     

     what should the recursive call be?

   • If the current call is

     trim("  hello    ")
     

     what should the recursive call be?

   Use these and other concrete cases to construct different possible recursive calls, and then include conditional code that makes the appropriate recursive call based on the current value of the input str.

Problem 7

1. I’m having trouble with the LetterSquare problem. Can you give us any hints on how to get started?

   Think back to the lecture and section materials on recursive backtracking. The basic idea behind recursive backtracking is that you have a number of variables that can each take on a number of possible values. (How does this relate to this problem? What are the variables? How many variables do you need?) You want to find values for these variables that fit your constraints. (What are the constraints in this problem? What requirement do the values of the variables need to fulfill?)

   A given invocation of the recursive-backtracking method uses a loop to consider all possible values for one of the variables. Once a value is successfully assigned to that variable, the method calls itself recursively, this time to consider all of the possible values for the next variable in the list (given the values of the variables they have already set). If you have successfully found values for all of the variables that fit the constraints, your terminating condition is met, and you can display the solution and return.

   If a particular value for a variable violates a constraint, you should skip that value and keep trying other values. If you run out of values for a variable, you should backtrack to the previous level of the recursion and go back to trying values for the previous variable.

2. I am struggling to apply the backtracking template from the lecture notes to the LetterSquare problem. I’m confused about what n and val in the template should mean in the context of this problem.

   As we said in the answer to the previous problem, recursive backtracking is a method for assigning values to a set of variables in light of a set of constraints. In the template, n tells you the variable that you’re currently trying to assign a value to, and val iterates over the set of possible values for that variable. (Note that n is not the variable itself - it is simply a parameter that allows you to determine the variable. For example, in the Queens problem, n was the number of row in which we were trying to place a queen, but we stored the actual values – i.e., the locations of the queens – in other data structures.)

   Another detail of the template that can vary is the way that the parameters to the method are modified in the recursive call. In the template, n is incremented by 1 to indicate that the recursive call will focus on the next variable. However, depending on the parameters that you decide to use for your method, you may need to modify them in some other way when you make the recursive call. The important thing is that the new parameters should reflect the subproblem that you’re trying to solve by making the recursive call, and the parameters should eventually reach one of the values that constitute a base case of the recursion.

3. I think my solveRB follows the template, but it isn’t finding a solution. Any suggestions?

   First, make sure that you have thoroughly tested your isValid method as described at the end of Task 2, since a faulty isValid will prevent your solveRB from working.

   Once you have a working isValid, trying adding temporary print statements to solveRB to see if you can figure out where things are going wrong.

   You can speed up testing by using temporary lines of code at the start of main. For example:

   String[] testSides = {"qxz", "hkl", "def", "uvw"};
   LetterSquare test = new LetterSquare(testSides);
   
   // start by just limiting things to a 2-word solution
   test.solveRB(0, 0, 2);
   
   // exit the program after testing
   System.exit(0);
   

   Two notes about our code above:

   • We have deliberately used a set of side strings that has very few possible words! This will limit the amount of output from your temporary print statements and make it easier to see if things are working correctly.

   • We have made a call to solveRB with a maxWords parameter of 2. This will also limit the amount of output. There isn’t a two-word solution to this puzzle – in fact, there isn’t even a ten-word solution! – but that’s okay. Our temporary print statement(s) should still allow us to see if we are correctly building up the individual words and if we are correctly making the transition from the first word to the second word when needed.

   One good starting point is to add the following print statement to the very beginning of your solveRB method:

   System.out.println(wordNum + " " + charNum + " " + Arrays.toString(this.words));
   

   Note that we print the wordNum and charNum parameters, along with the current contents of this.words. If this is the only temporary print statement that you add, and if you run the test code provided above, you should see something similar to the output in this file.

   It’s possible that you will get different output if you consider the letters in a different order than our solution does. But you should still get something comparable. In particular, each element of the words array should be either a valid full word or a valid prefix of a full word, and the letters in the words should observe all of the constraints of the puzzle.

   If you don’t see appropriate output, see if you can narrow down your issue by adding temporary print statements elsewhere in your code.

4. My solveRB is finding and printing a solution, but it doesn’t stop after it does so. Instead, it goes on and continues looking for other solutions. What am I doing wrong?

   As indicated in the problem description, your solveRB should include two different recursive calls: one to expand the current word, and one that will sometimes be used to move onto the next word. If either of these calls returns true, you must immediately return true. Otherwise, solveRB will continue looking for other solutions.

5. My solveRB is finding and printing a valid solution, but it has more words than the optimal solution. What am I doing wrong?

   Make sure that you have included a base case that checks for cases in which wordNum is too big, given the value of maxWords.

6. I’ve done some debugging, but I’m still not getting a valid solution. Any suggestions?

   Make sure that you are following the recursive-backtracking template from the lecture notes, but with the key differences noted in the problem description.

   In addition, you should check the following:

   • The base case that checks whether you have a solution should be checking that all letters are used and that the current word is full word of at least three letters.

   • Both of your recursive calls should come in between the call that you make to add a new letter and the call that you make to remove that letter.

   • You should only make the second recursive call if the current word is a full word of at least three letters.

Last updated on July 18, 2025.