0

My question is thus:

Suppose you have String myString = "SOME_CHARACTERS_THAT_NEED_MODIFICATION"; that you would want to have look like String modifiedString = "Some Characters That Need Modification". The "pure String" way to do it (and the case-independent way) would (optimize this as necessary):

//obtaining the locations of all the occurrences of '_'
int activeIndex = 0;
ArrayList <Integer> indexList = new ArrayList<Integer>();
while (activeIndex != -1)
{
    activeIndex = myString.indexOf('_', activeIndex + 1);
    indexList.add(new Integer(activeIndex));
}
//replacing all '_' with ' '
String tempString = myString.replace('_', ' ');
//declaring empty modifiedString
String modifiedString;
//lowercasing all characters that are not first characters of a word (here, a word is defined as being terminated by '_' or newline
for (int x = 0; x < indexList.size(); x++)
{
    modifiedString += tempString.substring(indexList.get(x), indexList.get(x)+1);
    if (x != indexList.size() - 1)
        //appending first uppercase character of word plus lowercased characters of the rest of the word
        modifiedString += tempString.subString(indexList.get(x)+1,indexList.get(x+1)).toLowerCase();
    else
        //we are near the end of the String (as far as ' ' is concerned)
        modifiedString += tempString.substring(index.get(x), tempString.length().toLowerCase());
}
//moving this modified String to modifiedString
modifiedString = tempString;

The other way I was proposing to do this would have been to dump myString into an array of characters, and then do array-based manipulation of all the characters. This would be easy in C++; a String is both an array of characters and an Object there! My question is, however, would both algorithms have the same complexity? //As a character array, I could probably do some arithmetic, assuming that the alphanumeric characters are numerically in the ASCII range (0 through 127). In fact, (int)uppercaseChar == (int)lowercaseChar - 32; for any of the uppercaseChar ranging from A-Z and any corresponding lowercaseChar ranging from a-z.

The char[] way to do would probably be something like (may need optimization)

//declaring necessary variables and containers
int activeIndex = 0;
ArrayList<Integer> indexList = new ArrayList<Integer>();

while (activeIndex != -1)
{
    //finding all '_'
    activeIndex = myString.indexOf('_', activeIndex + 1);
    //pushing it to indexArray
    indexArray.add(new Integer(activeIndex));
}
//dumping String to char[]
char[] charArray = myString.toCharArray();
for (int x = 0; x < indexArray.size(); x++)
{
    //making every '_' a ' '
    charArray[indexArray.get(x)] = ' ';
    //lowercasing every capitalized character that isn't a first character in a word
}
4

3 回答 3

2

两种算法是否具有相同的复杂性？

否。如果输入字符串包含n个连续的下划线，则

for (int x = 0; x < indexList.size(); x++)
    modifiedString += tempString.substring(indexList.get(x), indexList.get(x)+1);

将附加一个下划线n次。由于modifiedString每次循环都必须以线性时间成本复制旧值，因此整个算法需要二次时间。

相比之下，“char[]方法”需要线性时间。

于 2013-06-15T18:16:57.613 回答
1

我认为，通过 ASCII 或 unicode 方式来做会更好。

遍历数组，除第一个字符外，继续将所有字符替换为小写（通过您谈到的算术计算），直到找到一个ascii值与'_'相同的字符。一旦你得到这个字符，再次除了第一个字符，用小写替换其他所有内容，直到你再次得到'_'。这可以在一次迭代中完成。

而 string.replace all 本身只需要一次迭代即可替换。您的代码仍然看起来更干净。

注意：假设输入模式完全相同。

于 2013-06-15T18:21:22.740 回答
0

扩展@zerocool 的答案，我找到了以最佳方式执行此操作的代码。它是这样的：

private char[] charArray = myString.toCharArray();
int indexOfUnderscore = -1;
for (int x = 0; x < charArray.length; x++)
{
    if (charArray[x] == '_')
    {
        charArray[x] = ' ';
        indexOfUnderscore = x;
    }
    else
    {
        if (x > indexOfUnderscore + 1)
        {
            charArray[x] = (char)((int)charArray[x] + 32);
        }
    }
}

忽略 ，上述代码的算法复杂度为String.toCharArray()O(length)。然后我们可以说一些像private String modifiedString = new String(charArray);把它作为字符串取回的东西。我觉得字符数组的方式在语法上比内置的字符串函数更容易理解。

@zerocool，我希望当我想到这个时能看到你的答案。

于 2013-06-15T21:10:01.527 回答