[プログラマー][3回]圧縮(JAVA)

問題の説明
新進コミュニティはKakaoTalkで送信された情報を圧縮し,伝送効率を向上させる責任を負う.情報を圧縮しても伝達する情報は変えられないので,圧縮前の情報の完全回復を実現するための無損圧縮アルゴリズムを決定する.
Arpechは、複数の圧縮アルゴリズムにおいて、より性能が良く、より簡単なLZW(Lempel-Ziv-Welch)圧縮を実現することを決定する.LZW圧縮は1983年に発表されたアルゴリズムで、画像ファイルフォーマットGIFなど多様なアプリケーションで使用されている.
LZW圧縮は以下の過程を経る.
辞書は、長さが1のすべての単語を含む初期化されます.
辞書は、現在の入力と一致する最長文字列wを検索する.
wに対応する辞書のインデックス番号を出力し、入力からwを削除します.
入力に未処理の次の文字がある場合は、(c)、w+cに対応する単語を予め登録する.
手順2に戻ります.
圧縮アルゴリズムが英大文字のみを処理する場合、辞書は次のように初期化されます.辞書のインデックス番号は整数値で、1から始まるとします.
インデックス番号1 2 3... 24 25 26
単語A B C... X Y Z
例えばkakaoは入力として入ります.
現在、辞書にはKAKAOの1文字目Kが登録されているが、2文字目のKAには登録されていないため、1文字目Kに対応するインデックス番号11が出力され、次の文字Aを含むKAが辞書の27文字目として登録される.
2番目のアルファベットAは辞書にありますが、3番目のアルファベットのAKは辞書にないので、Aのインデックス番号1を出力し、AKは辞書に28番目に登録されています.
辞書には3文字目から始まるKAがあるので、次の文字Oを含むKAに対応するインデックス番号27、29番目の登録KAOが出力される.
最後に、未処理文字Oに対応するインデックス番号15が出力される.
現在の入力(w)次の文字(c)出力辞書(w+c)を追加
K A 11 27: KA
A K 1 28: AK
KA O 27 29: KAO
O 15
この過程を経て,5文字の文章KAKAOは4つのインデックス番号[11,1,27,15]に圧縮された.
TOBEORNOTTOBEORTOBEORNOTと入力すると、次のように圧縮されます.
現在の入力(w)次の文字(c)出力辞書(w+c)を追加
T O 20 27: TO
O B 15 28: OB
B E 2 29: BE
E O 5 30: EO
O R 15 31: OR
R N 18 32: RN
N O 14 33: NO
O T 15 34: OT
T T 20 35: TT
TO B 27 36: TOB
BE O 29 37: BEO
OR T 31 38: ORT
TOB E 36 39: TOBE
EO R 30 40: EOR
RN O 32 41: RNO
OT 34
入力フォーマット
入力として、英語の大文字のみからなる文字列msgが与えられる.msgの長さは1文字以上,1000文字以下である.
My Code

import java.util.*;
class Solution {
    public int[] solution(String msg) {
        List<Integer> list = new ArrayList<>();
        List<String> dict = new ArrayList<>();
        for(int i=0 ; i<msg.length() ; i++) {
            StringBuilder sb = new StringBuilder();
            sb.append(msg.charAt(i));
            while(i+1<msg.length() && dict.contains(sb.toString()+msg.charAt(i+1))) {
                i++;
                sb.append(msg.charAt(i));
            }
            if(sb.length()==1) list.add(msg.charAt(i)-'A'+1);
            else list.add(dict.indexOf(sb.toString())+27);
            if(i<msg.length()-1) dict.add(sb.toString()+msg.charAt(i+1));
        }
        int[] ret = new int[list.size()];
        for(int i=0; i<ret.length ; i++) ret[i] = list.get(i);
        return ret;
        }
}