Displaying all substrings of some given string

Question

I solved exercise 8 from Core Java for Impatient, chapter 1. This exercise is to implement a displayAllCombinations method to display all substrings of the given string.

I would like to prove that following algorithm is valid in Java. I wonder if there is an easier solution?

package pl.hubot.exercises.corejava.r01.ex08;

import java.util.Scanner;

/**
 * This program contains mine solutions of exercises
 * from book Core Java for the Impatient, chapter 1.
 *
 * The content of following exercise:
 * "Write a program that reads a string and displays all contained
 * in it non-empty strings."
 *
 * @version 1.00 23-07-2016
 * @author Hubot
 */
public class Program
{
    public static void main(String[] args)
    {
        System.out.print("Enter any string: ");
        Scanner in = new Scanner(System.in);
        String text = in.nextLine();
        displayAllCombinations(text);
    }

    private static void displayAllCombinations(String text)
    {
        int offset = 0;
        int current = 0;
        int ending = text.length();
        while (offset != ending)
        {
            String result = text.substring(current, ending - offset);
            if (!result.equals(""))
                System.out.println(result);
            if (current != (ending - offset)) current++;
            else
            {
                current = 0;
                offset++;
            }
        }
    }
}

Sample run:

Enter any string: Amy
Amy
my
y
Am
m
A

Answer 1

The variable names offset, current, and ending could be better. offset seems to be distance from the end, and current acts as a starting index, so the names should reflect that.

The loop logic is cryptic. There is a current = 0; offset++; that "resets" the loop, so it would be more clearly written with nested for loops instead.

If you do it right, you shouldn't need to check !result.equals(""). If you did need to check, then it would be better written as !result.isEmpty().

private static void displayAllCombinations(String text) {
    for (int end = text.length(); end > 0; end--) {
        for (int start = 0; start < end; start++) {
            System.out.println(text.substring(start, end));
        }
    }
}

Answer 2

        if (!result.equals(""))
            System.out.println(result);
        if (current != (ending - offset)) current++;
        else
        {
            current = 0;
            offset++;
        }

This is hard to read. On one occasion you've opted for no braces, same line, on another occasion you opted for no braces, multi-line, and later again you go for braces, multi-line.

Be consistent with the placement of your braces. It makes it easier to read the code.

    while (offset != ending)
    {
        String result = text.substring(current, ending - offset);
        if (!result.equals("")) 
        {
            System.out.println(result);
        }
        if (current != (ending - offset)) 
        {
            current++;
        }
        else
        {
            current = 0;
            offset++;
        }
    }

Beyond that, this program seems trivial and there's not much else to say about it.

There are, of course, various minor improvements we could make, such as...

• Storing ending - offset in a variable called endIndex and calling current beginIndex to match substring's argument names

• Rewriting the handling of beginIndex (current):

  beginIndex++;
  if (beginIndex== endIndex) 
  {
      beginIndex = 0;
      offset++;
  }
  

  This gets rid of the empty string case, whilst also simplifying your if-else statement.

• Then, since we no longer need to check if the substring is an empty string, we just print the substring directly.

Such improvements would leave you with a result like so:

private static void displayAllCombinations(String text)
{
    int offset = 0;
    int beginIndex = 0;
    int ending = text.length();
    while (offset != ending)
    {
        int endIndex = ending - offset;
        System.out.println(text.substring(beginIndex, endIndex));
        beginIndex++;
        if (beginIndex == endIndex) 
        {
            beginIndex = 0;
            offset++;
        }
    }
}

---

As for testing its correctness, I'd use unit tests, and instead of printing to screen, you add the strings to a List and return the list. Interesting cases are empty string, single character string, and a regular string like "Amy".

Answer 3

I know its kind of a late response but still if anybody finds it helpful.

I would like to suggest a slightly different approach, not much of a performance improvement but much easier to read.

---

This approach uses recursion. We just take a character out of the string one at a time, and every character have two choices :-

• Either it does not want to be part of the solution or
• It wants to be part of the solution.

so here's the code.

    public static void printSS(String ques, String ans) {
    if (ques.length() == 0) {
        System.out.println(ans);
        return;
    }
    char ch = ques.charAt(0);
    String restOfTheString = ques.substring(1);

    // char does not want to be part of the solution
    printSS(restOfTheString, ans + "");

    // char wants to be part of the solution
    printSS(restOfTheString, ans + ch);
}

And if you want to follow Single responsibility principle, here's a slightly different solution which returns an ArrayList of all possible compinations :-

public static ArrayList<String> getSS(String str) {
    if (str.length() == 0) {
        ArrayList<String> baseResult = new ArrayList<>();
        baseResult.add("");
        return baseResult;
    }

    char ch = str.charAt(0);
    String ros = str.substring(1);

    ArrayList<String> recursionResult = getSS(ros);
    ArrayList<String> myResult = new ArrayList<>();

    for (int i = 0; i < recursionResult.size(); i++) {
        myResult.add("" + recursionResult.get(i)); // ch says no
        myResult.add(ch + recursionResult.get(i)); // ch says yes
    }
    return myResult;
}