Learn how to implement a recursive Java method that splits a given string into all valid combinations of English words using a TreeSet<String> dictionary. Based on the WordSplitPrinter from Lecture 09, this solution explores substring paths, checks word validity, and prints valid word splits like "i saw a bus" from inputs such as "isawabus". Perfect for practicing recursion, backtracking, and set usage in Java.

How to Recursively Find All Valid Word Splits in a String Using a Dictionary Set in Java – WordSplit Algorithm with TreeSet

WordSplit Printer Material from Lecture 09 will be helpful here. In lecture, we talked about how we can use recursion exploration to print out all permutations of a given string. For example, we could use recursion on the input "goat" to print out: tgoa tgao toga goat gota gaot gato gtoa gtao ogat ogta oagt oatg otga otag agot agto aogt aotg atgo atog toag tago taog Most of these aren't actual anagrams, because they're gibberish. We could check which are actual words (like "toga"), but that wouldn't be enough. There are also cases like "atgo" where the full string isn't a word, but we can break it into the separate words "at" and "go". To find all anagrams, then, we need to find the ways we can take one of these permutations and split it into separate English words. That's where your method, findWordsplits, comes in: public void findWordSplits(String input, TreeSet<String> allWords) { // TODO: Implement this. } The method takes two parameters: input and allWords. input will be a string like "atgo" or "goat" that you're trying to split into separate words. You do not need to find permutations of input, since that was part of the demo we did in class. input will be a string whose character ordering is already set. allWords is a set containing the words listed in the "words.txt" file -- nearly 10,000 English words. allWords is already populated for you! You'll need to use it when you're splitting up the input string, since each chunk needs to be an actual word. . Your task is to implement findWordsSplits to find every way you can split input into valid English words, where every character in input is used exactly once. For example, if input is we would expect these two splits to be printed: "goat", go at goat Other arrangements, such as "g oat" or "goat", would not be printed because "g", "goa", and "t" are not considered words. The main method uses "isawabus" as input. Once findWordsSplits is correctly implemented, you should see the following output: i saw a bus i saw ab us is aw a bus is aw ab us If the exact ordering is not the same, that's completely fine. I've provided an already implemented method in the starter code called printWordsplit: public void printWordSplit(ArrayList<String> words) { // Already implemented for you. } You should call printWordSplit to print out a single arrangement. For the "i saw a bus" example above, you would call printWordSplit passing in an ArrayList<String> containing ["i", "saw", "a", "bus" ] to print it out. findWordSplits is a recursion exploration problem, just like our permutations demo in lecture. Think about how to apply the recursion exploration formula: 1. How do you represent a path of options you're exploring? o printWordsplit is a major hint -- if you need an ArrayList<String> to print a word split, that would also be a convenient way to represent a path. 2. At each step, what are your options? o Consider an example like "isawabus". We can actually list out every possible option for the next word: i is isa isaw isawa isawab isawabu isawabus Not all of these are words, so you'll need to check for yourself which ones are valid options using the allWords set. The TreeSet<String> is just a specific type of Set, so you can use any Set methods on it. 3. What do you do when you've finished exploring a path? o Just call printWordsplit! Another hint: in your implementation, you will need to use the String's substring method to split a string into two parts. • To get a substring that contains the first i characters, use str.substring(0, i) where str is the name of your String variable. To get the rest of that string (i.e. everything other than the first i characters), use str.substring(i). If you're struggling to translate the above into actual code, I strongly recommend revisiting Lecture 09 and see how we applied the same formula to the permutations problem or the password guessing problem. WordSplitChecker Material from Lecture 10 will be helpful here. If you were able to complete WordSplitPrinter, then congratulations! You've already done most of the hard work for this last step. In WordSplitChecker

Answer

import java.io.*;

import java.util.*;

public class WordSplitPrinter {

/**

* Finds and prints out every possible way to split the input String into individual, valid English words (including

* if input is itself a single valid word). You must call printWordSplit below to actually print out the results.

* Remember to implement a helper method, and have findWordSplits call that helper method.

public void findWordSplits(String input, TreeSet<String> allWords) {

//recursive function entry point

helper(input, allWords, "");

}

public void helper(String word, TreeSet<String> dict, String out) {

if (word.length() == 0) {

//output the combined words

printWordSplit(new ArrayList<String>(Arrays.asList(out.split(" "))));

return;

} else {

for (int i = 1; i <= word.length(); i++) {

String prefix = word.substring(0, i);

if (dict.contains(prefix)) {

helper(word.substring(i), dict, out + " " + prefix);

}

/**

* Prints out a word split, i.e. one particular arrangement of words. You should use this once you've finished

* exploring a potential word split and would like to print it out.

private void printWordSplit(ArrayList<String> words) {

if (words.isEmpty()) {

System.out.println("(empty word list)");

} else {

System.out.print(words.get(0));

for (int i = 1; i < words.size(); i++) {

System.out.print(" " + words.get(i));

}

System.out.println();

}

public static void main(String[] args) {

TreeSet<String> dictionary = readWords();

WordSplitPrinter wordSplitPrinter = new WordSplitPrinter();

// Expected to print out:

// i saw a bus

// i saw ab us

// is aw a bus

// is aw ab us

wordSplitPrinter.findWordSplits("isawabus", dictionary);

}

// Reads the "words.txt" file and returns the words in a TreeSet<String>. This is completely implemented for you!

private static TreeSet<String> readWords() {

TreeSet<String> allWords = new TreeSet<>();

try {

BufferedReader bufferedReader = new BufferedReader(new FileReader("words.txt"));

String line;

while ((line = bufferedReader.readLine()) != null) {

if (line.trim().isEmpty()) {

continue;

}

allWords.add(line.toLowerCase());

}

bufferedReader.close();

} catch (IOException exception) {

// print the absolute path of the file if it's not found

System.out.println(new File("words.txt").getAbsolutePath() + " is not found!");

throw new RuntimeException(exception);

}

return allWords;

}

Words.txt

the

and

for

that

this

with

you

not

are

from

your

all

have

new

was

will

home

can

about

page

has

free

but

our

one

other

information

time

they

site

may

what

which

their

news

out

use

any

there

see

only

his

when

contact

here

business

who

web

also

now

help

get

view

online

first

been

would

how

were

services

some

these

click

its

service

than

find

price

date

back

top

people

had

list

name

just

over

state

year

day

into

two

health

world

used

work

last

most

products

music

buy

data

make

them

should

product

system

post

her

city

add

policy

number

such

please

available

support

message

after

best

software

then

jan

good

video

well

where

info

rights

public

books

high

school

through

each

links

she

review

years

order

very

privacy

book

items

company

read

group

need

many

user

said

does

set

under

general

research

university

january

mail

full

map

reviews

program

life

know

games

way

days

management

part

could

great

united

hotel

real

item

international

center

ebay

must

store

travel

comments

made

development

report

off

member

details

line

terms

before

hotels

did

send

right

type

because

local

those

using

results

office

education

national

car

design

take

posted

internet

address

community

within

states

area

want

phone

dvd

shipping

reserved

subject

between

forum

family

long

based

code

show

even

black

check

special

prices

website

index

being

women

much

sign

file

link

open

today

technology

south

case

project

same

pages

version

section

own

found

sports

house

security

both

county

american

photo

game

members

power

while

care

network

down

computer

systems

three

total

place

end

following

download

him

without

per

access

think

north

resources

current

posts

big

media

law

control

water

history

pictures

size

art

personal

since

including

guide

shop

📩 Need a similar solution? Email me: adel455@hotmail.com

How to Recursively Find All Valid Word Splits in a String Using a Dictionary Set in Java – WordSplit Algorithm with TreeSet

Answer

📩 Need a similar solution? Email me: adel455@hotmail.com

Comments

Nepali Graphics - Learn design, Animation, and Progrmming

Contact form