Hi I need help fixing this OutOfMemoryError for my WordLadder program. Basically I after being halfway through the input wordladder file which contains the start and end words to create the world ladders it slows down significantly and the error occurs. I believe the error is due to the creation of several stacks without removal of already used ones.
The error occurs at Line: 74 in the WordStack file in the getNewStacks method which, as the name says, is supposed to get new stacks.
Below are all the required files:
Dictionary txt:
https://drive.google.com/file/d/1vl6N4-3IYK86lGxmf0hqP7nX2e0BYrim/view?usp=sharing
input txt:
https://drive.google.com/file/d/1ahHBL0ivqhC0zh24DCFnar03hxTt7Awc/view?usp=sharing
WordLadder main:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class WordLadder {
public static void main(String args[]) throws FileNotFoundException {
Dictionary dictionary = new Dictionary(new File("dictionary.txt"));
Scanner scan = new Scanner(new File("input.txt"));
while (scan.hasNextLine()) {
String start = scan.next();
String stop = scan.next();
System.out.println(findLadder(start, stop, dictionary));
}
}
static String findLadder(String start, String end, Dictionary dictionary) {
if (!dictionary.contains(start) || !dictionary.contains(end)) {
return "No word ladder between \"" + start + "\" and \"" + end + "\".";
}
if (start.equals(end)) return start + " " + end;
LinkedList stackQueue = new LinkedList();
stackQueue.enqueue(new WordStack(start, end));
boolean continueSearch;
boolean success = false;
WordStack ladder = new WordStack();
do {
int queueSize = stackQueue.size();
continueSearch = false;
for (int stackIndex = 0; stackIndex < queueSize; stackIndex++) {
LinkedList newStacks = ((WordStack) stackQueue.dequeue()).getNewStacks(dictionary);
if (newStacks.size > 0) {
while (newStacks.size() > 0) {
WordStack next = (WordStack) newStacks.dequeue();
if (next.success()) {
success = true;
ladder = next;
break;
}
stackQueue.enqueue(next);
}
continueSearch = true;
}
if (success) break;
}
if (success) break;
} while (continueSearch);
if (success) return ladder.toString();
else return "No word ladder between \"" + start + "\" and \"" + end + "\".";
}
}
WordStack (location of error line 74) :
public class WordStack {
LinkedList words;
String targetWord;
boolean success;
WordStack() {
words = new LinkedList();
targetWord = "";
success = false;
}
WordStack(LinkedList list, String target) {
words = list;
targetWord = target;
success = false;
}
WordStack(String startWord, String target) {
words = new LinkedList();
words.push(startWord);
targetWord = target;
success = false;
}
int size() {
return words.size();
}
void push(String word) {
words.push(word);
}
void add(String word) {
push(word);
}
String pop() {
if (size() < 1) return null;
return (String) words.pop();
}
String topWord() {
return (String) words.peek();
}
WordStack deepCopy() {
return new WordStack(words.hardCopy(), targetWord);
}
void markSuccess() {
success = true;
}
boolean success() {
return success;
}
boolean contains(String word) {
WordStack compare = deepCopy();
while (compare.size() > 0) {
if (word.equals(compare.pop())) return true;
}
return false;
}
LinkedList getNewStacks(Dictionary dictionary) {
LinkedList stacks = new LinkedList();
for (int letterPos = 0; letterPos < topWord().length(); letterPos++) {
for (char letter = 'a'; letter <= 'z'; letter++) {
String newWord = topWord().substring(0, letterPos) + letter + topWord().substring(letterPos + 1, topWord().length());
if (dictionary.contains(newWord) && !contains(newWord)) {
WordStack newStack = deepCopy();
newStack.push(newWord);
if (newWord.equals(targetWord)) newStack.markSuccess();
stacks.enqueue(newStack);
}
}
}
return stacks;
}
public String toString() {
String returnString = "";
for (int index = size() - 1; index >= 0; index--) {
returnString += (String) words.getPeek(index) + " ";
}
return returnString;
}
}
Node class:
public class Node {
public Object data;
Node next;
Node() {
data = null;
next = null;
}
Node(Object data) {
this.data = data;
next = null;
}
Object get() {
return data;
}
void set(Object data) {
this.data = data;
}
Node getNextPtr() {
return next;
}
void setNextPtr(Node next) {
this.next = next;
}
public String toString() {
return "" + data;
}
}
LinkedList:
public class LinkedList {
Node head;
Node tail;
int size;
LinkedList() {
head = null;
tail = null;
size = 0;
}
LinkedList hardCopy() {
LinkedList copy = new LinkedList();
if(size() < 1) return copy;
Node current = head;
while(current.getNextPtr() != null) {
copy.addEnd(current.get());
current = current.getNextPtr();
}
copy.addEnd(current.get());
return copy;
}
void iterateHead() {
head = head.getNextPtr();
size--;
}
void addEnd(Object newObj) {
enqueue(newObj);
}
void add(Object newObj) {
Node newNode = new Node(newObj);
if(size == 0) {
head = newNode;
}
else {
newNode.setNextPtr(head);
head = newNode;
}
size++;
}
Object peek() {
return head.get();
}
void push(Object newObj) {
add(newObj);
}
void enqueue(Object newObj) {
Node newNode = new Node(newObj);
if(size < 1) {
head = newNode;
tail = newNode;
} else {
tail.setNextPtr(newNode);
tail = newNode;
}
size++;
}
Object pop() {
Node pop = head;
if(size > 1) {
head = head.getNextPtr();
size--;
return pop.get();
}
else if(size == 1) {
size--;
head = null;
return pop.get();
}
else return null;
}
Object dequeue() {
if(size < 1) return null;
Node dequeueNode = head;
if(size > 1) {
iterateHead();
}
else {
head = null;
tail = null;
size--;
}
return dequeueNode.get();
}
int size() {
return size;
}
Object getPeek(int index) {
if(index >= size) return null;
Node current = head;
for(int i = 0; i < index; i++) {
current = current.getNextPtr();
}
Object data = current.get();
return data;
}
}
I do apologize for the amount of required code for the program to run.
