Created
July 5, 2019 19:08
-
-
Save alun/e23145041993cfd5172971256911fd79 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import javafx.util.Pair; | |
import org.testng.annotations.Test; | |
import java.util.*; | |
import static org.testng.Assert.*; | |
public class Sol { | |
static Set<Map<Integer, Integer>> indexPointers(String s) { | |
Set<Map<Integer, Integer>> result = new HashSet<>(); | |
for (int i = 0; i < s.length(); i++) { | |
Map<Integer, Integer> indexPointer = new TreeMap<Integer, Integer>(); | |
for (int j = 0; j < s.length(); j++) { | |
if (j != i) { | |
indexPointer.put(j, s.codePointAt(j)); | |
} | |
} | |
result.add(indexPointer); | |
} | |
return result; | |
} | |
public static boolean hasPath(List<String> words, String first, String last) { | |
Map<Map<Integer, Integer>, Set<String>> index = new HashMap<>(); | |
Set<String> wordsSet = new HashSet<>(words); | |
if (!wordsSet.contains(first)) return false; | |
if (!wordsSet.contains(last)) return false; | |
for (String word : words) { | |
for (Map<Integer, Integer> indexPointer : indexPointers(word)) { | |
Set<String> indexWords = index.getOrDefault(indexPointer, new HashSet<>()); | |
indexWords.add(word); | |
index.put(indexPointer, indexWords); | |
} | |
} | |
Deque<String> found = new LinkedList<>(); | |
found.addFirst(first); | |
while (found.size() > 0) { | |
String word = found.removeFirst(); | |
wordsSet.remove(word); | |
for (Map<Integer, Integer> indexPointer : indexPointers(word)) { | |
Set<String> nextWords = index.get(indexPointer); | |
for (String nextWord : nextWords) { | |
if (nextWord.equals(last)) return true; | |
if (wordsSet.contains(nextWord)) { | |
found.addLast(nextWord); | |
} | |
} | |
} | |
} | |
return false; | |
} | |
static int editDistance(String s1, String s2) { | |
int result = 0; | |
for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) { | |
result += s1.codePointAt(i) == s2.codePointAt(i) ? 0 : 1; | |
} | |
return result; | |
} | |
public static int hasPath2(List<String> words, String first, String last) { | |
Set<String> wordsSet = new HashSet<>(words); | |
if (!wordsSet.contains(first)) return -1; | |
if (!wordsSet.contains(last)) return -1; | |
Deque<Pair<String, Integer>> found = new LinkedList<>(); | |
found.addFirst(new Pair(first, 0)); | |
while (found.size() > 0) { | |
Pair<String, Integer> elem = found.removeFirst(); | |
String word = elem.getKey(); | |
Integer distance = elem.getValue(); | |
wordsSet.remove(word); | |
for (String next : wordsSet) { | |
if (editDistance(word, next) == 1) { | |
if (next.equals(last)) return distance + 1; | |
found.addLast(new Pair<>(next, distance + 1)); | |
} | |
} | |
} | |
return -1; | |
} | |
@Test | |
public static void checkHasPath() { | |
List<String> dict = Arrays.asList( | |
"BARE", | |
"CARE", | |
"CASE", | |
"CASK", | |
"BASK", | |
"RATE", | |
"MATE", | |
"MANE", | |
"BANE", | |
"BONE", | |
"XYZF" | |
); | |
assertTrue(hasPath(dict, "BARE", "BASK")); | |
// assertTrue(hasPath2(dict, "BARE", "BASK")); | |
assertTrue(hasPath(dict, "BASK", "BARE")); | |
assertEquals(hasPath2(dict, "BASK", "BARE"), 4); | |
assertFalse(hasPath(dict, "BARE", "XYZF")); | |
// assertFalse(hasPath2(dict, "BARE", "XYZF")); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment