search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

[QZ5] Adjacent Entity Case #136

Closed jbaek3 closed 3 years ago

jbaek3 commented 3 years ago

Should our code be able to handle two adjacent entities without a space in between? Such as "AlbaniaSouth Sudan". I couldn't figure out how to make this case work because end_index of Albania is exclusive and overlaps with the begin_index of South_Sudan.

My code: https://github.com/jbaek3/dsa-java/blob/master/dsa-java/src/main/java/edu/emory/cs/trie/TrieQuiz.java Failed test with adjacent case: https://github.com/jbaek3/dsa-java/blob/master/dsa-java/src/test/java/edu/emory/cs/trie/TrieQuizTest.java

marvinquiet commented 3 years ago

Please look at the example Trie tree which includes a space there. So if there is a word without spaces, then you may not match that. But in this case, if these two are both countries in the trie tree, you need to match both.

lujiaying commented 3 years ago

~To me, in the case you mentioned you can ignore "South Sudan", but only extract the first entity "Albania".~

Sorry, the previous statement is wrong.

Remind the "abcCananda" case, we also want to extract "Canada" out. (Reference: https://github.com/emory-courses/dsa-java/issues/124)

jbaek3 commented 3 years ago

Thank you, I figured it out. I had forgotten to assign the next potential word's beginIndex to the current index for when the child is a completed word as well as when it does not exist.