[개발자매일영어] Tries - Cracking Coding Interview

이번에는 Tries Interview Question에 대한 내용 입니다.
앞으로는 코딩 인터뷰 문제도 한문제씩 같이 풀어보도록 하겠습니다. 제일 아래에 기출문제가 있습니다. 같이 풀어봐요!

영어 공부는 왕도는 없습니다. 매일 꾸준히 듣고 말하기 연습 하는 것이 가장 중요합니다.

개발자매일영어는 당분간은 Cracking Coding Interview의 저자로 유명한 Gayle Laakmann McDowell저자의 강좌를 지속적으로 공부해보도록 하겠습니다.
전체 분량은 너무 길어서 주요부분 한 두 군데만 1분 이하로 발췌하여 mp3파일로 만들고 있습니다.
즉 한 주제당 1분 이하 분량의 mp3파일이 한 두개씩 제공되겠습니다. 나머지 부분은 리스닝 연습 하시면 되겠습니다.
이번에는 따라하기 쉽도록 최대한 짧게 잘랐습니다.

공부하는 3단계 방법은 아래와 같습니다.

1. 1분 이하 분량을 번역
2. 전체 듣기 두번
3. 문장 듣고 따라 말하기 두번
   하루에 한시간 이상 들으면서 말하기 연습하면 좋을 것 같습니다.
   *** 개발자 매일 영어는 제가 개인적으로 공부하기 위해 만든 mp3파일을 혹시 다른 분에게도 도움이 될까 해서 공유하고 있는 것입니다. 부족한 영어 실력으로 번역한 것이라 잘못되었을 수도 있습니다. 이상한 부분은 댓글로 알려 주시면 감사하겠습니다. ***

mp3 파일 다운로드: https://drive.google.com/open?id=19SoHC0YKrg8nRB2C-XjoCu49a9P1-Fbn
원본:

----- mp3 script -----
There's one optimization that often comes up in try problems.
Suppose you had a situation where a user was typing a word and as soon as the
word became, and it clearly was going to be an invalid word, you want to say
underline it.
Someone types C and you say yes that is, in fact, it potentially going to be a valid word and then someone types CA. Ok great, looking good.
Now they type CAL. Yes okay, there's words that start with CAL, now they type CALP, oops no.
That's an error. So that's a good place to use a try. Now the way that I would
explain tries so far, you would do each of these lookups from scratch.
You would say is there a C, is that a valid prefix, yes it is, and then you do is C A a valid prefix and you start from scratch over at the root.
Now in a lot of cases though we actually want these calls to kind of build on each other so one thing we can do with our try is we can keep state in various ways so when we look up is C a valid prefix, we actually store where we are in the tree.
So when we, when the user types the very next character, an A, we just look immediately is A a child rather of C of that last look up rather than starting from scratch.
There's different ways you can actually implement that. One way you can do it is
to actually keep state within the try. Another way you could do that is actually return the node back to the caller.
So when I say is C a valid prefix, I get not only that's a valid prefix but I also get information that gives me exact reference to that node.
Then rather than saying starting from the root and saying is CA a valid prefix I just ask is A a child of C, and then I ask is L a child of the CA etc

-- 번역 예 (직접번역 해보세요) --
try 문제들에 자주 나오는 한가지 최적화 방법이 있습니다.
사용자가 단어 입력중 단어가 되었을때 이것은 분명히 잘못 된 단어였고 당신은 밑줄을 긋고 싶은 상황이었다고 생각해보세요.
누군가가 C를 입력하면 그것은 잠재적으로 유효한 단어가 되고 또 CA를 입력합니다. 좋아요. 잘한 것 같아요. 그리고 CAL을 입력합니다. CAL로 시작하는 단어들이 있습니다. CALP를 입력합니다. 오 틀렸군요. 그건 실수입니다. 그건 try를 사용하기에 좋은 곳입니다. 지금까지 설명한 tries 방법을 사용해 첨부터 검색할 수도 있습니다. 거기에 C가 있고 그것은 유효한 접두사고 CA도 유효한 접두사고 그렇게 첨부터 검색해 나갈 수 있습니다.
많은 상황에서 우리는 실제로 일종의 서로서로 구성하는 이런 호출들을 원하지만 try를 사용해 할 수 있는 한가지가 다양한 방법으로 상태를 유지할 수 있는 것입니다. C가 유효한 접두어라는 것을 찾았을 때 그곳 트리에 실제 저장할 수 있습니다. 사용자가 바로 다음 글자로 A를 입력하면 A가 마지막 검색에서 C의 자식이라는 것을 첨부터 바로 알 수 있어 첨부터 검색하는 것 보다 낳습니다. 그걸 실제로 구현하기 위한 몇가지 방법들이 있습니다. 하나는 실제로 try에 상태를 유지하는 것입니다. 다른 방법은 호출자에 해당 node를 돌려주는 방법이 있습니다. C가 유효한 접두어라면 유효한 접두어라는 것을 얻을 뿐만 아니라 그 node에 대한 참조를 얻을 수 있습니다. 루트부터 찾는것 보다 낫습니다. CA가 유효한 접두어고 A가 C의 자식이란걸 물었고 L이 CA의 자식인것을 물을 수 있습니다.
----- 이주의 Interview Question (같이 풀어 봐요!) -----
Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.

문제 링크: https://leetcode.com/problems/add-and-search-word-data-structure-design/description/