LeetCode之Shortest Distance to a Character（Kotlin）

2019-03-04 423 阅读1分钟

问题： Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

S string length is in [1, 10000].
C is a single character, and guaranteed to be in string S.
All letters in S and C are lowercase.

方法：先正向遍历，遍历出S中所有字符正向距离C的距离，然后反向遍历，遍历出S中所有字符反向距离C的距离，最后取正向距离和反向距离的最小值的集合即为最终结果。

具体实现：

class ShortestDistanceToACharacter {
    fun shortestToChar(S: String, C: Char): IntArray {
        val result = mutableListOf<Int>()
        var pre = Int.MIN_VALUE / 2
        for (index in S.indices) {
            if (S[index] == C) {
                pre = index
            }
            result.add(index - pre)
        }
        pre = Int.MAX_VALUE / 2
        for (index in S.lastIndex downTo 0) {
            if (S[index] == C) {
                pre = index
            }
            result[index] = Math.min(result[index], pre - index)
        }
        return result.toIntArray()
    }
}

fun main(args: Array<String>) {
    val shortestDistanceToACharacter = ShortestDistanceToACharacter()
    val S = "loveleetcode"
    val C = 'e'
    CommonUtils.printArray(shortestDistanceToACharacter.shortestToChar(S, C).toTypedArray())
}

有问题随时沟通

具体代码实现可以参考Github