Wortleiter gesamter Programmcode
-
Hallo,
jeder kennt doch bestimmt das Wortleiterspiel. Man hat ein Startwort und ein Endwort und soll eine Wortleiter bilden.
Hier der Code dazu. Viel Freude damit
//main.java public class main { public static void main(String[] args) { Wordladder wordladder = new Wordladder(); } }
//Wordladder.java import java.util.ArrayList; import java.util.Queue; import java.util.LinkedList; public class Wordladder { String [] dictionary = new String[]{"tears","spile","spars","spare","sears","spire","smile"}; String startWord = "tears"; String endWord = "smile"; Queue<ArrayList<String>> queue = new LinkedList<ArrayList<String>>(); public Wordladder() { ArrayList<String> root = new ArrayList<String>(); root.add(startWord); queue.add(root); while(!queue.isEmpty()) { ArrayList<String> current = queue.remove(); for(int i = 0 ; i < current.size();i++) { for(int j = 0 ; j < dictionary.length;j++) { if( isNeighbor(current.get(i),dictionary[j]) ) { if(current.get(i).equals(endWord)) { String ausgabe = ""; for(int k = 0 ; k< current.size();k++) { if(k < current.size()-1) ausgabe +=current.get(k)+" - "; else ausgabe +=current.get(k); } System.out.println("Wordladder"); System.out.println(ausgabe); return; } if(!current.contains(dictionary[j])) { ArrayList<String> partialLadder = new ArrayList<String>(current.size()+1); copyArrayList(current, partialLadder); partialLadder.add(dictionary[j]); queue.add(partialLadder); } } } } } } public boolean isNeighbor(String str1, String str2) { int count = 0; for(int i =0;i < str1.length();i++) { if(str1.charAt(i) != str2.charAt(i) ) { count++; } if(count >1 || (str1.length() != str2.length())) { return false; } } return true; } private void copyArrayList(ArrayList<String> src, ArrayList<String> dst) { for(int i = 0;i < src.size();i++ ) { dst.add(src.get(i)); } } }
-
Für die copyArrayList-Funktion kannst du Collections.copy nehmen.
--> https://www.tutorialspoint.com/java/util/collections_copy.htmUnd ein Bug ist auch drin: Zeile 33 -> das == muss .equals heißen. Dass es bei dir auch mit == funktioniert, liegt daran, dass der Compiler den Code optimiert (Mehrfachverwendung von immutable Objekten). Aber mit == checkst du nur die Referenzen auf Gleichheit. Bei zwei verschiedenen Strings mit gleichem Inhalt geht das schief.
-
ok. Danke Zeile 33 schon korrigiert
Bin für jeden Review dankbar
-
Here is wordladder with Depth First - Search Algorithm
import java.util.ArrayList; public class Wordladder { String [] dictionary = new String[]{"tears","spile","spars","teari","lears","sears","spire","spare","smile"}; String startWord = "tears"; String endWord = "smile"; public Wordladder() { ArrayList<String> list = new ArrayList<String>(); list.add(startWord); dfs(list); } public void dfs(ArrayList list) { int lastElement = list.size()-1; for(int i=0;i<dictionary.length;i++) { if(isNeighbor(dictionary[i],list.get(lastElement).toString()) && !list.contains(dictionary[i])) { ArrayList<String> list2 = new ArrayList<String>(); copyArrayList(list, list2) ; list2.add(dictionary[i]); if(dictionary[i].equals(endWord)) { String ausgabe = ""; for(int k = 0 ; k< list2.size();k++) { if(k < list2.size()-1) ausgabe +=list2.get(k)+" - "; else ausgabe +=list2.get(k); } System.out.println("Wordladder"); System.out.println(ausgabe); return; } dfs(list2); } } } public boolean isNeighbor(String str1, String str2) { int count = 0; for(int i =0;i < str1.length();i++) { if(str1.charAt(i) != str2.charAt(i) ) { count++; } if(count >1 || (str1.length() != str2.length())) { return false; } } return true; } private void copyArrayList(ArrayList<String> src, ArrayList<String> dst) { for(int i = 0;i < src.size();i++ ) { dst.add(src.get(i)); } } }
-
Welcher Algorithmus findet die kuerzeste Loesung. Welcher Algorithmus findet die Loesung am schnellsten.
Breadth First Search findet die kuerzeste Loesung allgemeinhin zuerst.
Depth First Search findet die Loesung am schnellsten.
-
Hier noch die Depth First Search Iterative Loesung
import java.util.ArrayList; import java.util.Stack; public class Wordladder { //String [] dictionary = new String[]{"tears","spile","spars","lears","sears","teari","spire","spare","smile"}; String [] dictionary = new String[]{"tears","sears","bears","seare"}; String startWord = "tears"; String endWord = "seare"; ArrayList<String> list = new ArrayList<String>(); public Wordladder() { list.add(startWord); dfsIterativ(list); } public void dfsIterativ(ArrayList<String> list1) { Stack<Object> stack = new Stack(); stack.push(0); stack.push(list.size()-1); stack.push(list1); while(!stack.empty()) { ArrayList<String> list = (ArrayList)stack.pop(); int lastElement = (int)stack.pop(); int indexDictionary = (int)stack.pop(); for(int i=indexDictionary;i<dictionary.length;i++) { if(isNeighbor(dictionary[i],list.get(lastElement).toString()) && !list.contains(dictionary[i])) { if(dictionary[i].equals(endWord)) { list.add(dictionary[i]); String ausgabe = ""; for(int k = 0 ; k< list.size();k++) { if(k < list.size()-1) ausgabe +=list.get(k)+" - "; else ausgabe +=list.get(k); } System.out.println("Wordladder"); System.out.println(ausgabe); break; } ArrayList<String> list3 = new ArrayList<String>(); copyArrayList(list, list3); stack.push(i+1); stack.push(list3.size()-1); stack.push(list3); list.add(dictionary[i]); stack.push(0); stack.push(list.size()-1); stack.push(list); break; } } } } public void dfs(ArrayList list) { int lastElement = list.size()-1; for(int i=0;i<dictionary.length;i++) { if(isNeighbor(dictionary[i],list.get(lastElement).toString()) && !list.contains(dictionary[i])) { list.add(dictionary[i]); if(dictionary[i].equals(endWord)) { String ausgabe = ""; for(int k = 0 ; k< list.size();k++) { if(k < list.size()-1) ausgabe +=list.get(k)+" - "; else ausgabe +=list.get(k); } System.out.println("Wordladder"); System.out.println(ausgabe); return; } dfs(list); } } } public boolean isNeighbor(String str1, String str2) { int count = 0; for(int i =0;i < str1.length();i++) { if(str1.charAt(i) != str2.charAt(i) ) { count++; } if(count >1 || (str1.length() != str2.length())) { return false; } } return true; } private void copyArrayList(ArrayList<String> src, ArrayList<String> dst) { for(int i = 0;i < src.size();i++ ) { dst.add(src.get(i)); } } }
-
Hier der korriegierte Code fuer den breadth first Search. Hatte nee for schleife zuviel drin
//Wordladder.java import java.util.ArrayList; import java.util.Queue; import java.util.LinkedList; public class Wordladder { String [] dictionary = new String[]{"tears","spile","spars","teari","lears","sears","spire","spare","smile"}; String startWord = "tears"; String endWord = "smile"; Queue<ArrayList<String>> queue = new LinkedList<ArrayList<String>>(); public Wordladder() { bfs(); } public void bfs() { ArrayList<String> root = new ArrayList<String>(); root.add(startWord); queue.add(root); while(!queue.isEmpty()) { ArrayList<String> current = queue.remove(); for(int j = 0 ; j < dictionary.length;j++) // process dictionary for each queue { if( isNeighbor(current.get(current.size()-1),dictionary[j]) ) { if(current.get(current.size()-1).equals(endWord)) { String ausgabe = ""; for(int k = 0 ; k< current.size();k++) { if(k < current.size()-1) ausgabe +=current.get(k)+" - "; else ausgabe +=current.get(k); } System.out.println("Wordladder"); System.out.println(ausgabe); break; } if(!current.contains(dictionary[j])) { ArrayList<String> partialLadder = new ArrayList<String>(current.size()+1); copyArrayList(current, partialLadder); partialLadder.add(dictionary[j]); queue.add(partialLadder); } } } } } public boolean isNeighbor(String str1, String str2) { int count = 0; for(int i =0;i < str1.length();i++) { if(str1.charAt(i) != str2.charAt(i) ) { count++; } if(count >1 || (str1.length() != str2.length())) { return false; } } return true; } private void copyArrayList(ArrayList<String> src, ArrayList<String> dst) { for(int i = 0;i < src.size();i++ ) { dst.add(src.get(i)); } } }