Monday, August 8, 2016

Google – Letter to Letter Probability

Google – Letter to Letter Probability

b之后出现a的概率为1/2，b之后结束的概略为1/2
[Solution]

 `class` `Solution {`   `  ``int``[][] matrix = ``new` `int``[``27``][``27``];` `  ``int``[] rowSum = ``new` `int``[``26``];`   `  ``public` `Solution(String[] words) {` `    ``for` `(String s : words) {` `      ``for` `(``int` `i = ``1``; i < s.length(); i++) {` `        ``char` `prev = s.charAt(i - ``1``);` `        ``char` `curr = s.charAt(i);`   `        ``matrix[prev - ``'a'``][curr - ``'a'``]++;` `        ``rowSum[prev - ``'a'``]++;` `      ``}` `      ``char` `last = s.charAt(s.length() - ``1``);` `      ``matrix[last - ``'a'``][``26``]++;` `      ``rowSum[last - ``'a'``]++;` `    ``}` `  ``}`   `  ``public` `void` `insert(String word) {` `    ``for` `(``int` `i = ``1``; i < word.length(); i++) {` `      ``char` `prev = word.charAt(i - ``1``);` `      ``char` `curr = word.charAt(i);`   `      ``matrix[prev - ``'a'``][curr - ``'a'``]++;` `      ``rowSum[prev - ``'a'``]++;` `    ``}` `    ``char` `last = word.charAt(word.length() - ``1``);` `    ``matrix[last - ``'a'``][``26``]++;` `  ``}`   `  ``public` `double` `rateQuery(``char` `a, ``char` `b) {` `    ``if` `(b == ``'#'``) {` `      ``return` `(``double``) matrix[a - ``'a'``][``26``] / rowSum[a - ``'a'``];` `    ``}` `    ``return` `(``double``) matrix[a - ``'a'``][b - ``'a'``] / rowSum[a - ``'a'``];` `  ``}` `}`