Google – Letter to Letter Probability

Google – Letter to Letter Probability
给一个dictionary, [aba, acb], find the letter to letter probability
比如a之后出现b的概率为1/3, a之后出现c的概率为1/3, a之后结束的概率也为1/3
b之后出现a的概率为1/2，b之后结束的概略为1/2
[Solution]
就是maintain一个27 * 27的matrix来统计出现次数。可以再加一个rowSum[] array来优化query time to O(1)

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'];   } }

Read full article from Google – Letter to Letter Probability