[Leetcode] 249。グループシフトされた文字列
249 Group Shifted Strings
実際、この質問は、トリックを理解するのにそれほど煩わしいことではありません。重要なのは、実際には、結果の各セットをベースケースに抽出できるということです。
理由はこれです。最初のグループを例にとってみましょう。たとえば、 'abc' => 'bcd' => 'xyz'
その中で、1つのルールはba = cb = dc = 1です。またはxa = yb = zc = 23です。つまり、bcdは左に1回シフトする限りabcになり、xyzはそれがあればabcになります。 23回左にシフトします。このグループの基本ケースとして、最初の文字がaである文字列を取り上げます。最初の文字とaの間の距離を計算するだけで、文字列全体が左にシフトされてベースケースのグループになる回数がわかります。次に、ハッシュテーブルを使用してチームメンバーを維持します。 (グループメンバーはベースケースを含まない場合があります)
たとえば、abc、efg、bdf、efi
1. abcでは、aとaの間の距離が0であるため、文字列を左に移動する必要はありません。これは基本ケースです。ハッシュテーブルにグループabcがあり、メンバーはabcです。
2. efgでは、eとaの間の距離は4であるため、文字列を4スペース左にシフトする必要があります。その後、abcのベースケースになり、ハッシュテーブルのabcグループにメンバーefgを追加します。
3. bdf、b、およびaの間の距離は1であるため、文字列全体が1だけ左にシフトされて、aceのベースケースになり、ハッシュテーブルに追加のグループaceがあります。メンバーはbdfです
4. efi、eとaの間の距離は4なので、全体の左シフトは4倍になり、エースになります。したがって、ハッシュテーブルにエースグループの別のメンバーを追加して、激しくefiします。
これまでのところ、各グループの値の部分は、問題に必要なリストソリューションセットです。過度の左シフトによって引き起こされるオーバーレンジを回避するために再度注意してください。回避するには26を追加する必要があります。与えられたコードは次のとおりです。
public List groupStrings(String[] strings) { Map strMap = new HashMap() for (String str : strings) { String shiftedKey = _getShiftedString(str) if (!strMap.containsKey(shiftedKey)) strMap.put(shiftedKey, new LinkedList()) strMap.get(shiftedKey).add(str) } return new LinkedList(strMap.values()) } private String _getShiftedString(String a) { if (a.length() > 0) { char[] cArr = a.toCharArray() int diff = (int)cArr[0] - 'a' cArr[0] = 'a' for (int i = 1 i = diff) ? (int)cArr[i] - diff : (int)cArr[i] - diff + 26) } return new String(cArr) } else { return a } }