936. Stamping The Sequence


Posted by hata0833 on 2022-08-22

You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'.

In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp.

For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:
place stamp at index 0 of s to obtain "abc??",
place stamp at index 1 of s to obtain "?abc?", or
place stamp at index 2 of s to obtain "??abc".
Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s).
We want to convert s to target using at most 10 * target.length turns.

Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 * target.length turns, return an empty array.

大意:用章蓋出target,可以把蓋過的覆蓋掉,如有章abc,在2號位蓋一次章 => ??abc,在0號位再蓋一次章 => abcbc,求怎麼蓋才可以蓋出目標,印章必須全部印上,不可以只蓋ab或a,如果蓋不了返回空數組
連續兩天每日挑戰都是hard,要吐了...

思路:看到的是蓋完的結果,要逆著推回去蓋的過程,所以先從完整的開始找,依次逆推回去,最後判斷能不能還原
討論區有人畫圖,看起來就很直觀

target:  a b a b a b c b c b a b a b c b c


layer 1:          a b c           a b c    
layer 2:      a b c   a b c   a b c   a b c
layer 3:  a b c           a b c
 pass 1:  a b a b a b c b c b a b a b c b c
                  ^ ^ ^           ^ ^ ^

 pass 2:  a b a b * * * b c b a b * * * b c
              ^ ^ ^   ^ ^ ^   ^ ^ ^   ^ ^ ^

 pass 3:  a b * * * * * * * b * * * * * * *
          ^ ^ ^           ^ ^ ^

 pass 4:  * * * * * * * * * * * * * * * * *

from https://leetcode.com/problems/stamping-the-sequence/discuss/1135739/JS-Python-Java-C%2B%2B-or-Easy-Reverse-Matching-Solution-w-Explanation

var movesToStamp = function(stamp, target) {
    const res = [], s = stamp.split(''), t = target.split('');
    let fit = false, j, i, stampping = true;
    // 確認還能不能蓋章,不能就跳出
    while (stampping) {
        // 由於蓋章必須蓋滿,所以只需要走到target.length - s.length
        for (i = 0, stampping = false; i <= target.length - s.length; i++) {
            for (j = 0, fit = false; j < s.length; j++) {
                if (t[i + j] == '*') {
                    continue;
                } else if (s[j] != t[i + j]) {
                    break;
                } else {
                    fit = true; // 代表有任一的是必須蓋的,排除掉 *** 的情況
                }

            }
            if (fit && j == s.length) {
                for (let k = i; k < s.length + i; k++) {
                    t[k] = '*';
                }
                res.push(i);
                stampping = true;
            }

        }

    }
    // 如果蓋完的情況下還有蓋不了的地方,返回空數組
    return t.findIndex(x => x != '*') == -1 ? res.reverse() : [];
};

#Leetcode







Related Posts

[MSSQL] 小量資料轉excel #格式跑掉

[MSSQL] 小量資料轉excel #格式跑掉

閉包 Closure

閉包 Closure

[ CSS 04 ] 圖片設定相關

[ CSS 04 ] 圖片設定相關


Comments