LeetCode算法题709解题思路

2019年03月18日 |

原题

709. To Lower Case

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

Example 1:

1 2	Input: "Hello" Output: "hello

Example 2:

1 2	Input: "here" Output: "here"

Example 3:

1 2	Input "LOVELY" Output: "lovely"

思路

看到这道题，我首先脑袋里想到的是Golang的strings包里的ToLower方法。
但是如果是这样的话实现的意义又是啥呢？

于是我就想到了ASCII码，查到ASCII码表里，A=65,Z=90。然后把str转换成rune，rune是int32的别名，于是就可以通过比较大小来判断每个字符是否是大写字母，通过观察可以得知大小写对应的字母差值是32。有了这些条件，我想答案也就明了了。

老规矩，先自己实现，不要直接看结果。

实现

Golang实现

https://github.com/cook-coder/my-leetcode-solution/tree/master/easy/709

嘚瑟

709 嘚瑟

再次思考

这是一道非常简单的题，我提交完之后试图在Discuss里面看看别人是如何讨论和评价的，但是没看到啥有价值的东西。
但是却看到了一个人真的是用strings.ToLower()来实现的，而且成绩也是超越了100%，但是作者并没有说清楚是时间还是空间上的超越，我就怀疑人生了，这个题目到底有没有意义啊。

先抛开题目不谈，我看了strings.ToLower()的实现：

func ToLower(s string) string {
    isASCII, hasUpper := true, false
    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= utf8.RuneSelf {
            isASCII = false
            break
        }
        hasUpper = hasUpper || (c >= 'A' && c <= 'Z')
    }

    if isASCII { // optimize for ASCII-only strings.
        if !hasUpper {
            return s
        }
        b := make([]byte, len(s))
        for i := 0; i < len(s); i++ {
            c := s[i]
            if c >= 'A' && c <= 'Z' {
                c += 'a' - 'A'
            }
            b[i] = c
        }
        return string(b)
    }
    return Map(unicode.ToLower, s)
}

这段代码有几个关键点：

c >= utf8.RuneSelf

查看源码知道：RuneSelf = 0x80，即十进制128.
什么意思呢？代码里面也表达的很清楚了，>= RuneSelf就不是ASCII码。
这时就要借助一下ASCII码表，可以发现表的范围在0~127之间。

如果字符全是ASCII码

则直接执行这对ASCII码优化的代码
此时程序而外创建了一个[]byte的slice来存储转为小写字母的字符串，我猜测会比我的程序多占用一些内存。
后面我用strings.Lower()跑了几次，内存消耗在1.9MB和2.0MB之间浮动，所以，而我的一直保持在1.9M。
但并不是要说我的程序好，只是验证我的判断而已。

否则执行unicode的ToLower方法来转换字符串

这里的意义在哪呢，比如法文的大小写转换，我实现的方式只适用于英文字母的大小写转换。
法文État的É的值为201，那么就会被我的程序忽略而不进行转换，而strings.ToLower()就可以兼容这种转换。

所以作为一段健壮的程序来说，strings.ToLower()无疑是最优选择。但如果场景是指针对ASCII码表以内的话，我们也可以自己来实现一段针对特定场景优化的代码。