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)
Read full article from 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']; }} |
