在O(1)中用Java反转一个字符串？

Question

在给定CharSequence的情况下,标准Java库中是否有任何工具在O(1)时间内产生反转？

I guess this is "easy" to implement, just wondering whether it already exists. (I suspect the reason this is not offered is because the "easy" way would actually break multi-char code-points - but in many cases we know we are not dealing with those).

Thanks

Update Heh, it's a bit amusing that most thought this "impossible", good work guys! Well, actually it is (conceptually) trivial - pseudojava follows to make it clear:

class MyReverseString extends String { //of course I can't extend String!
   final String delegate;
   MyReverseString(String delegate) { this.delegate = delegate; }

   int length() { return delegate.length(); }

   int charAt(int i) { return delegate.charAt(delegate.length() - 1 - i); }
}

I'm leaving the question open for some more, just in the rare event that something like the obvious solution (e.g. see Jon Skeet's one) already exists in the JDK and someone knows about it. (Again, highly unlikely due to those nasty code points).

Edit Probably the confusion came from me having "string" in the title (but not String!), whereas I only ask for "the reverse of a CharSequence". If you were confused, sorry. I would have hoped the O(1) part would make exactly clear what was being asked for.

And by the way, this was the question that made me ask this one. (That's a case where it would be easier to run a regex from right-to-left, not left-to-right, so there may be some practical value even for the simple/broken-codepoints implementation)

Answer 1

Well, you can easily produce an implementation of CharSequence which returns the same length, and when asked for a particular character returns the one at length-index-1. toString() becomes O(n) of course...

Creating that reversed CharSequence would be O(1) - all it's got to do is store a reference to the original CharSequence, after all. Iterating over all the characters within the sequence is going to be O(n) though, obviously.

请注意,创建逆转CharSequence(根据你的问题的机构)是不一样创建一个颠倒String(按照标题你的问题).实际上生成字符串是O(n),必须是.

示例代码,大部分未经测试:

public final class ReverseCharSequence implements CharSequence
{
    private final CharSequence original;

    public ReverseCharSequence(CharSequence original)
    {
        this.original = original;
    }

    public int length()
    {
        return original.length();
    }

    public char charAt(int index)
    {
        return original.charAt(original.length() - index - 1);
    }

    public CharSequence subSequence(int start, int end)
    {
        int originalEnd = original.length() - start;
        int originalStart = original.length() - end;
        return new ReverseCharSequence(
            original.subSequence(originalStart, originalEnd));
    }

    public String toString()
    {
        return new StringBuilder(this).toString();
    }
}

Answer 2

This is impossible. In order to reverse a string you must process each character at least once, thus, it must be at least O(n).

Answer 3

string result = new StringBuffer(yourString).reverse().toString();

Depending on what you understand under O(1) it does not seem possible since even reading the string once needs O(n) with n being the number of characters in the string.