925-長按鍵入

wenhai.he 發(fā)布于2019-08-16 13:27 / 1931人閱讀

摘要：前言的第一題長按鍵入你的朋友正在使用鍵盤輸入他的名字。偶爾，在鍵入字符時，按鍵可能會被長按，而字符可能被輸入次或多次。示例輸入輸出解釋中的和被長按。

前言

Weekly Contest 107的第一題長按鍵入：

你的朋友正在使用鍵盤輸入他的名字 name。偶爾，在鍵入字符 c 時，按鍵可能會被長按，而字符可能被輸入 1 次或多次。
你將會檢查鍵盤輸入的字符 typed。如果它對應(yīng)的可能是你的朋友的名字（其中一些字符可能被長按），那么就返回 True。
示例 1：

輸入：name = "alex", typed = "aaleex"
輸出：true
解釋："alex" 中的 "a" 和 "e" 被長按。

示例 2：

輸入：name = "saeed", typed = "ssaaedd"
輸出：false
解釋："e" 一定需要被鍵入兩次，但在 typed 的輸出中不是這樣。

示例 3：

輸入：name = "leelee", typed = "lleeelee"
輸出：true

示例 4：

輸入：name = "laiden", typed = "laiden"
輸出：true
解釋：長按名字中的字符并不是必要的。

提示：

name.length <= 1000

typed.length <= 1000

name 和 typed 的字符都是小寫字母。

解題思路

這道題我是先使用了一個壓縮算法把字符串進(jìn)行壓縮后再對比，這個壓縮算法就是參考游程編碼。而且在LeetCode上也有對應(yīng)的題目，如443. 壓縮字符串。而我的專欄中也有相關(guān)算法的文章900-RLE 迭代器。這個算法處理后，會將字符串壓縮到一個數(shù)組中，該數(shù)組的偶數(shù)位索引對應(yīng)的值為字符，奇數(shù)位索引對應(yīng)的值為該字符重復(fù)出現(xiàn)的次數(shù)。
后續(xù)只需要判斷對應(yīng)位置的字符是否相等以及出現(xiàn)次數(shù)即可。

實現(xiàn)代碼

    /**
     * 925. 長按鍵入
     * @param name
     * @param typed
     * @return
     */
    public boolean isLongPressedName(String name, String typed) {
        boolean result=true;
        if(typed.length()>=name.length()){//輸入字符串的長度必須不小于原字符串
            List names=compress(name);
            List typeds=compress(typed);
            if(names.size()==typeds.size()){//壓縮后的數(shù)組長度必須一致
                for(int i=0;i<=names.size()-2;i=i+2){
                    if(names.get(i).equals(typeds.get(i))){
                        int nameTimes=Integer.valueOf(names.get(i+1));
                        int typedTimes=Integer.valueOf(typeds.get(i+1));
                        if(typedTimes compress(String str){
        List result=new ArrayList<>();
        char currentChar = 0;
        int currentIndex=0;
        for(int i=0;i