java - 删除字符串的第一个字符 O(1)

Question

如何在 java 中表示一个字符串，以便删除字符串的第一个字符需要 O(1) 时间？

这个问题:on string character removing讨论在 Java 中使用子字符串删除字符串的第一个字符。但正如在这里找到的on Java 7 changes子字符串实现现在运行时间为 O(字符串长度)。如何使用 Java 删除 O(1) 中的第一个字符？

如果可能的话，我只是想要一个替代方案，使用处理字符串和字符的任何其他类似的类，如 StringBuffer、StringBuilder 等。或者任何其他方式，肯定有一种方法可以在 O(1) 中删除单词的第一个字符。

Answer 1

如果不先复制字符串，就无法获取它们，这需要 O(n) 时间，因为它必须遍历整个字符串才能复制它......除非您使用反射(reflection)。

现在您谈论替换字符串中的第一个字母和互换地替换字符串中每个单词的第一个字母。如果你想替换每个单词的第一个字母，你将不得不遍历整个字符串，这是 O(n) 时间 - 没有其他方法。

如果你只想替换第一个字母，你可以使用反射，但我不建议你实际这样做，而只是使用 .substring(String)。

您正在寻找的方法:

/**
 * Replaces the first letter in a {@code String} in O(1) time.
 *
 * This uses reflection to change the values and will modify the
 * {@code String}s values. 
 *
 * @param str the {@code String} to modify.
 * @param letter the new first letter of the {@code String}.
 * @return {@code str}
 */
public static String replaceFirstLetter(String str, char letter) {
    if (str == null) {
        throw new NullPointerException("str cannot be null");
    }

    if (str.length() == 0) {
        throw new IllegalArgumentException("String cannot be empty");
    }

    try {
        Field value
                = str.getClass().getDeclaredField("value");

        value.setAccessible(true);

        Field modifiersField = Field.class.getDeclaredField("modifiers");
        modifiersField.setAccessible(true);
        modifiersField.setInt(value, value.getModifiers() & ~Modifier.FINAL);

        char[] values = (char[]) value.get(str);
        values[0] = letter;
        value.set(str, values);

    } catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException ex) {
        ex.printStackTrace();
        //This should never happen
    }

    return str;
}

请注意，此方法将修改您传入的 String，因此这会破坏 String 类的不可变规则，不应在生产代码中使用。而且，仅横向穿过字符串可能比使用此方法更快。

public static void main(String[] args) {
    String s = "Hello";
    replaceFirstLetter(s, 'Y');
    System.out.println(s);

    System.out.println(replaceFirstLetter("Hello", 'G'));
}

这很好地证明了这一点。