文字列の反転アルゴリズムと実装

文字列の反転

問題1：文字配列の反転

文字配列として与えられた入力文字列を反転する関数を実装してください。追加の配列を割り当てず、入力配列をその場で変更し、O(1)の追加スペースのみを使用してこの問題を解決する必要があります。

例1：

入力：s = ["h","e","l","l","o"]
出力：["o","l","l","e","h"]

例2：

入力：s = ["H","a","n","n","a","h"]
出力：["h","a","n","n","a","H"]

考え方：

双ポインタ（two-pointer）の手法を用います。一つは先頭を指し、もう一つは末尾を指します。この二つのポインタが指す要素を交換します。

コード：

public void reverseString(char[] s) {
    int 開始 = 0;
    int 終了 = s.length - 1;
    while (開始 < 終了) {
        char 一時 = s[開始];
        s[開始] = s[終了];
        s[終了] = 一時;
        開始++;
        終了--;
    }
}

問題2：チャンク単位の文字列反転

文字列 `s` と整数 `k` が与えられます。文字列の先頭から `2k` 文字ごとに、その `2k` 文字の中で先頭の `k` 文字を反転させます。

残りの文字が `k` 文字未満の場合、残りの文字をすべて反転させます。
残りの文字が `2k` 未満だが `k` 以上の場合、先頭の `k` 文字を反転させ、残りの文字はそのままにします。

例1：

入力：s = "abcdefg", k = 2
出力："bacdfeg"

例2：

入力：s = "abcd", k = 2
出力："bacd"

考え方：

難点は、文字列を個々のチャンクに分離する方法です。forループの反復条件を少し変更し、増分を常に `2k` に設定することで、各チャンクを個別に処理できます。

コード：

まず、部分反転を行うヘルパーメソッドを定義します。

private void 部分反転(char[] ch, int i, int j) {
    while (i < j) {
        char 一時 = ch[i];
        ch[i] = ch[j];
        ch[j] = 一時;
        i++;
        j--;
    }
}

次に、メインの反転ロジックを実装します。

public String reverseStr(String s, int k) {
    char[] ch = s.toCharArray();
    for (int i = 0; i < ch.length; i += 2 * k) {
        if (i + k <= ch.length) {
            部分反転(ch, i, i + k - 1);
            continue;
        }
        部分反転(ch, i, ch.length - 1);
    }
    return new String(ch);
}

問題3：単語の順序を反転させる

文字列 `s` が与えられます。この文字列の中の単語の順序を反転させた結果を返してください。

「単語」は空白文字でない文字からなる文字列です。`s` は少なくとも一つの空白文字で単語を区切っています。

返される結果の文字列では、単語の間には一つの空白文字のみが含まれ、先頭や末尾の空白、または単語間の複数の空白は含まれません。

例1：

入力：s = "the sky is blue"
出力："blue is sky the"

例2：

入力：s = "  hello world  "
出力："world hello"

例3：

入力：s = "a good   example"
出力："example good a"

考え方：

空白文字の処理が重複点です。単語の反転だけでなく、単語間の空白を一つだけにする必要があるため、専用の空白削除メソッドと、全体の文字列を反転させた後、個々の単語を反転させるメソッドが必要になります。

具体的なコードを例に説明します：

reverseStringメソッド

StringBuilderオブジェクト `sb` の `start` から `end` のインデックスにある文字シーケンスを反転させます。

private void reverseString(StringBuilder sb, int start, int end) {
    while (start < end) {
        char temp = sb.charAt(start);
        sb.setCharAt(start, sb.charAt(end));
        sb.setCharAt(end, temp);
        start++;
        end--;
    }
}

removeSpaceメソッド

このメソッドは、先頭と末尾の空白を削除し、単語間の余分な空白を削除して、一つの空白のみを残すようにします。

private StringBuilder removeSpace(String s) {
    int start = 0;
    int end = s.length() - 1;
    while (s.charAt(start) == ' ') {
        start++;
    }
    while (s.charAt(end) == ' ') {
        end--;
    }
    StringBuilder sb = new StringBuilder();
    while (start <= end) {
        char c = s.charAt(start);
        if (c != ' ' || sb.length() == 0 || sb.charAt(sb.length() - 1) != ' ') {
            sb.append(c);
        }
        start++;
    }
    return sb;
}

reverseEachWordメソッド

文字列内の各単語の文字順序を反転させますが、単語間の順序は変更しません。

private void reverseEachWord(StringBuilder sb) {
    int n = sb.length();
    int start = 0;
    int end = 0;
    while (start < n) {
        while (end < n && sb.charAt(end) != ' ') {
            end++;
        }
        reverseString(sb, start, end - 1);
        start = end + 1;
        end = start;
    }
}

reverseWordsメソッド

文字列内の各単語の文字順序を反転させ、単語間の順序は保持します。

public String reverseWords(String s) {
    StringBuilder sb = removeSpace(s);
    reverseString(sb, 0, sb.length() - 1);
    reverseEachWord(sb);
    return sb.toString();
}

タグ: 文字列操作アルゴリズム双ポインタ法 Java stringbuilder

6月23日 19:49 投稿

異端開発室

文字列の反転アルゴリズムと実装