Long Pressed Name
给两个string, 一个是typed, 一个是name, 求一个是不是想输入name, 但是长按几个字符后, 变成了typed.
这题我用的是run length encode, 先encode两个变成a1b1c2这种形式, 然后看是不是length一样, 再看是不是name的数字小于typed的数字, 除此之外, 就是true.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
class Solution { class Pair{ Pair(char c, int a){ this.c = c; this.a = a; } public String toString() { return this.c + " " + this.a; } char c; int a; } public boolean isLongPressedName(String name, String typed) { LinkedList<Pair> a = encode(name); LinkedList<Pair> b = encode(typed); if(a.size() != b.size()) return false; int n = a.size(); for(int i = 0; i < n; i++) { Pair ca = a.get(i); Pair cb = b.get(i); if(ca.c != cb.c) return false; if(ca.a > cb.a) return false; } return true; } public LinkedList<Pair> encode(String s){ LinkedList<Pair> list = new LinkedList<>(); for(char c : s.toCharArray()){ if(list.isEmpty()) list.addLast(new Pair(c, 1)); else{ Pair pre = list.removeLast(); if(c == pre.c){ pre.a++; list.addLast(pre); }else { list.addLast(pre); list.addLast(new Pair(c, 1)); } } } return list; } } |