ExpressiveWords [source code]

public class ExpressiveWords {
static
/******************************************************************************/
class Solution {
    public int expressiveWords(String S, String[] words) {
        char[][] s_info = parse (S);
        int count = 0;
        loop1 : for (String word : words) {
            char[][] w_info = parse (word);
            if (w_info.length != s_info.length)
                continue;
            for (int i = 0; i < s_info.length; i++) {
                if (w_info[i][0] != s_info[i][0])
                    continue loop1;
                if (!(w_info[i][1] == s_info[i][1] || 
                    (s_info[i][1] > w_info[i][1] && s_info[i][1] >= 3 + '0')))
                    continue loop1;
            }
            count++;
        }
        return count;
    }

    char[][] parse (String word) {
        List<Character> letters = new ArrayList<> ();
        List<Integer> lens = new ArrayList<> ();
        Character cur = null;
        Integer cur_count = null;
        for (Character c : word.toCharArray ()) {
            if (cur == null) {
                cur = c;
                cur_count = 1;
            } else if (cur == c) {
                cur_count++;
            } else {
                letters.add (cur);
                cur = c;
                lens.add (cur_count);
                cur_count = 1;
            }
        }
        letters.add (cur);
        lens.add (cur_count);
        char[][] res = new char[letters.size ()][2];
        for (int i = 0; i < letters.size (); i++) {
            res[i][0] = letters.get (i);
            res[i][1] = (char) (lens.get (i) + '0');
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ExpressiveWords.Solution tester = new ExpressiveWords.Solution();
        String[][] inputs = {
            {"heeellooo"}, {"hello", "hi", "helo"}, {"1"},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            System.out.println (Printer.separator ());
            String S = inputs[3 * i][0];
            String[] words = inputs[3 * i + 1];
            int ans = Integer.parseInt (inputs[3 * i + 2][0]), output = tester.expressiveWords (S, words);
            System.out.printf ("%s and %s\n%s, expected: %d\n", 
                S, Printer.array (words), Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

感觉这题考察的是一个思路, 而不是复杂度, 所以直接开始人逻辑分析这个问题本身就行了;

依然是一个很简单的题目, 依然是磕磕巴巴搞了半天, 真的丢人, 有思路的题目居然都不能秒解;

2018-05-01 21:19:32 回头看看这个题目的题目描述啰嗦其实也是一个难点;

然后parse函数设计还算是比较讲道理吧, 就是一个分段, 搞成一个类似run length compression的技术; 这个好像Sedgwick上面有更好的办法; 不过能搞出来就行, 一个分段算法能够完成一个压缩的结果就行了; Sedgwick那个结果我记得是比较复杂的, 除非自己实现过很多次很熟练了, 不然面试的时候不要轻易的说你会写;

然后这个分段也是我最熟悉的写法, 里面三个branch, 初始化, in run, not in run. 然后最后注意收尾就行了; 这个问题场景下不是很难;

我这个分段算法好像也不好, 我记得Sedgwick上面写分段, 比如开run的时候, 他是把count初始化到0, 然后下面就可以统一一个count++; 不过这个也是小细节;

另外即使是我这个写法, 第一个branch是初始化, 第三个branch是下降沿, 这两个branch的代码实际上重复率还是挺高的; 最后返回一个array实际上也不是特别有必要, 直接两个list主要是不好返回;

这题算法还是有点啰嗦的, 这个也是refdash面试的时候面试官的一个反馈; 不过这种临场写的没见过的题目的代码, 这个也是难以避免的问题;

主体逻辑还是简单的, 这种在if header写很长的, 面试的时候感觉确实是容易踩坑.

editorial

Approach #1: Run Length Encoding [Accepted]

Intuition

For some word, write the head character of every group, and the count of that group. For example, for "abbcccddddaaaaa", we'll write the "key" of "abcda", and the "count" [1,2,3,4,5].

Let's see if a word is stretchy. Evidently, it needs to have the same key as S.

Now, let's say we have individual counts c1 = S.count[i] and c2 = word.count[i].

• If c1 < c2, then we can't make the ith group of word equal to the ith word of S by adding characters.
• If c1 >= 3, then we can add letters to the ith group of word to match the ith group of S, as the latter is extended.
• Else, if c1 < 3, then we must have c2 == c1 for the ith groups of word and S to match.

class Solution {  
    public int expressiveWords(String S, String[] words) {  
        RLE R = new RLE(S);  
        int ans = 0;  

        search: for (String word: words) {  
            RLE R2 = new RLE(word);  
            if (!R.key.equals(R2.key)) continue;  
            for (int i = 0; i < R.counts.size(); ++i) {  
                int c1 = R.counts.get(i);  
                int c2 = R2.counts.get(i);  
                if (c1 < 3 && c1 != c2 || c1 < c2)  
                    continue search;  
            }  
            ans++;  
        }  
        return ans;  
    }  
}  

class RLE {  
    String key;  
    List<Integer> counts;  

    public RLE(String S) {  
        StringBuilder sb = new StringBuilder();  
        counts = new ArrayList();  

        char[] ca = S.toCharArray();  
        int N = ca.length;  
        int prev = -1;  
        for (int i = 0; i < N; ++i) {  
            if (i == N-1 || ca[i] != ca[i+1]) {  
                sb.append(ca[i]);  
                counts.add(i - prev);  
                prev = i;  
            }  
        }  

        key = sb.toString();  
    }  
}

awice这个解法最后也是跟我一样, 有点啰嗦的; 他用一个class来封装最后的压缩结果, 还可以; 用个array搞的跟真的一样, 是有点烦人; 尤其是面试的时候, 自己容易出错, 面试官看的还想骂人;

这个分段算法还是awice的标志性写法, 跟我一样, 喜欢用下降沿trigger的方法来写, 但是他的一个特色是喜欢把下降沿跟最后的收尾写到一起;

然后prev还是他习惯的一个anchor写法: 用来计算长度;

用StringBuilder来当做专门适用于char的一个LinkedList, 也是一个思路吧, 看看就行这个;

主函数的逻辑跟我实在是太像了;

复杂度是多少呀? 是QK, Q是length of words. 这个也不难分析吧. 空间复杂度是O(K).

https://leetcode.com/problems/expressive-words/discuss/121741/Short-straight-forward-C++-solution-two-pointers-one-pass-scan

For each word to be tested, scan from left to right and check if whenever a mismatched character is reached in S three identical characters also present.

int expressiveWords(string S, vector<string>& words) {  
    int res = 0;  
    for (auto &w : words)  
        if (w.size() <= S.size()) {  
            int i, j;  
            for (i = 0, j = 0; j < S.size(); j++) {  
                if (w[i] == S[j]) // w[i] references to a null char when i reaches w.size()  
                    i++;  
                else if (j > 0 && S[j] == S[j - 1] && j + 1 < S.size() && S[j] == S[j + 1]) // last, this and next  
                    j++;  
                else if (!(j > 1 && S[j] == S[j - 1] && S[j] == S[j - 2])) // this and last 2 chars  
                    break;  
            }  
            if (i == w.size() && j == S.size()) // both pointers reach the end  
                res++;  
        }  
    return res;  
}

实际的逻辑有点复杂, 虽然最后代码是很简洁的; 大概看了一下, 感觉有点类似subSequence算法的那种思路; 两个指针平行移动;

不过我大概思考了一下, 他这个算法有一个问题就是在扫的时候, i和j至少有一个要走到头, 你看他中间根本没有提前...不对

另外注意他这里也有一个conditonal ++++的操作: j有可能一个iteration里面走两步; 这种写法以前也见过, 有点坑爹的; 好像就是那个KMP写法;

以及, 你看他的第一个branch, 实际上是一个i和j同时++的操作; 非要这样写; 不过两个变量, 实际上之前也见过这种写法, 一个要作为主要变量, 就是这里的i, 一般是一个无条件前进的变量, 然后另外一个变量的advance的方法就灵活一些;

首先i和j一起从一个比如两个word里面都是A的地方开始; 然后因为都相等, 比如w开头是AAA, 然后S开头是AAAAAA, 那么两个一起走到3的位置, 然后不相等了, 这个时候执行branch2, 然后j会++++, 走到6, 正好把所有的A走完, 然后继续比较下一个run, 这个逻辑还是不错的; 他为什么控制这里j要++++, 是因为比如w有A, 然后S有AAA, 这个是能保证合格的一个最少的条件, 假如是A和AA, 那么第二branch无法执行, 第三也无法执行, 直接就break掉, 最后被跳过;

具体的算法逻辑还是值得分析, 反正这个设计确实是挺牛逼的;

UNFINISHED

uwi:

class Solution {  
    public int expressiveWords(String S, String[] words) {  
        int[][] fs = tof(S);  
        int ct = 0;  
        outer:  
        for(String w : words){  
            int[][] f = tof(w);  
            if(fs.length != f.length)continue;  
            for(int i = 0;i < f.length;i++){  
                if(fs[i][0] != f[i][0])continue outer;  
                if(fs[i][1] >= 3){  
                    if(f[i][1] <= fs[i][1]){  
                    }else{  
                        continue outer;  
                    }  
                }else{  
                    if(f[i][1] == fs[i][1]){  
                    }else{  
                        continue outer;  
                    }  
                }  
            }  
            ct++;  
        }  
        return ct;  
    }  

    int[][] tof(String s)  
    {  
        int n = s.length();  
        int[][] ret = new int[n][];  
        int p = 0;  
        for(int i = 0;i < n;i++){  
            if(i == 0 || s.charAt(i) != s.charAt(i-1)){  
                ret[p++] = new int[]{s.charAt(i), 1};  
            }else{  
                ret[p-1][1]++;  
            }  
        }  
        return Arrays.copyOf(ret, p);  
    }  
}

没仔细看, 感觉跟我差不多吧;

Problem Description

Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii". Here, we have groups, of adjacent letters that are all the same character, and adjacent characters to the group are different. A group is extended if that group is length 3 or more, so "e" and "o" would be extended in the first example, and "i" would be extended in the second example.

题目描述比较唬人. 看到这里以为这个extended是让我去做一个什么事情, 其实这里的extended就是一个形容词的意思;

As another example, the groups of "abbcccaaaa" would be "a", "bb", "ccc", and "aaaa"; and "ccc" and "aaaa" are the extended groups of that string.

For some given string S, a query word is stretchy if it can be made to be equal to S by extending some groups. Formally, we are allowed to repeatedly choose a group (as defined above) of characters c, and add some number of the same character c to it so that the length of the group is 3 or more. Note that we cannot extend a group of size one like "h" to a group of size two like "hh" - all extensions must leave the group extended - ie., at least 3 characters long.

Given a list of query words, return the number of words that are stretchy.

Example:

Input:   
S = "heeellooo"  
words = ["hello", "hi", "helo"]  
Output: 1  
Explanation:   
We can extend "e" and "o" in the word "hello" to get "heeellooo".  
We can't extend "helo" to get "heeellooo" because the group "ll" is not extended.

Notes:

• 0 <= len(S) <= 100.
• 0 <= len(words) <= 100.
• 0 <= len(words[i]) <= 100.
• S and all words in words consist only of lowercase letters

Difficulty:Medium
Total Accepted:2.7K
Total Submissions:7.8K
Contributor:awice
Companies
google
Related Topics
string