LeetCode242/567.字符串的排列:有效的字母异位词(Kotlin语言)

一个会写诗的程序员

发布于 2020-04-24 17:11:59

5840

文章被收录于专栏：一个会写诗的程序员的博客一个会写诗的程序员的博客

LeetCode242.有效的字母异位词

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram" 输出: true 示例 2:

输入: s = "rat", t = "car" 输出: false 说明: 你可以假设字符串只包含小写字母。

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解题思路

其实就是判断两个字符串的 1.所有组成的字符集完全相同 2.所有字符集出现的次数完全相同

代码

class Solution {
    fun isAnagram(s1: String, s2: String): Boolean {
        val w = s1.length
        val n = s2.length
        if (w != n) return false

        var i = 0
        while (i + w <= n) { // 注意这里是 i + w <= n
            if (checkOK(s1, s2, i, w)) {
                return true
            }
            i++
        }
        return false
    }


    /**
     * 检查 s1 的排列是否在当前窗口 substr = s2.substr(i,i+w+1)
     */
    fun checkOK(s1: String, s2: String, i: Int, w: Int): Boolean {
        val substr = s2.substring(i, i + w)

        // 1.s1 的字符集跟substr字符集完全相同
        val map1 = s1.groupBy { it }
        val map2 = substr.groupBy { it }

        val keyset1 = map1.keys
        val keyset2 = map2.keys
        if (keyset1.size != keyset2.size) return false
        for (k in keyset1) {
            if (!keyset2.contains(k)) {
                return false
            }
        }

        // 2.s1 各个字符出现的次数与 substr 各个字符出现的次数完全相等
        for ((k, v1) in map1) {
            val v2 = map2[k]
            if (v1.size != v2?.size) {
                return false
            }
        }

        return true

    }
}

变式题: 567. 字符串的排列

https://leetcode-cn.com/problems/permutation-in-string/

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").

示例2:

输入: s1= "ab" s2 = "eidboaoo" 输出: False

注意：

输入的字符串只包含小写字母两个字符串的长度都在 [1, 10,000] 之间

源代码

/**
 * 滑动窗口法
 */
fun checkInclusion(s1: String, s2: String): Boolean {
    val w = s1.length
    val n = s2.length
    if (w > n) return false

    var i = 0
    while (i + w <= n) { // 注意这里是 i + w <= n
        if (checkOK(s1, s2, i, w)) {
            return true
        }
        i++
    }
    return false
}

/**
 * 检查 s1 的排列是否在当前窗口 substr = s2.substr(i,i+w+1)
 */
fun checkOK(s1: String, s2: String, i: Int, w: Int): Boolean {
    val substr = s2.substring(i, i + w)

    // 1.s1 的字符集跟substr字符集完全相同
    val map1 = s1.groupBy { it }
    val map2 = substr.groupBy { it }

    val keyset1 = map1.keys
    val keyset2 = map2.keys
    if (keyset1.size != keyset2.size) return false
    for (k in keyset1) {
        if (!keyset2.contains(k)) {
            return false
        }
    }

    // 2.s1 各个字符出现的次数与 substr 各个字符出现的次数完全相等
    for ((k, v1) in map1) {
        val v2 = map2[k]
        if (v1.size != v2?.size) {
            return false
        }
    }

    return true

}

fun main() {

    run {
        val s1 = "ab"
        val s2 = "eidbaooo"
        val ans = checkInclusion(s1, s2)
        println(ans)
    }

    run {
        val s1 = "ab"
        val s2 = "eidboaoo"
        val ans = checkInclusion(s1, s2)
        println(ans)
    }

    run {
        val s1 = "adc"
        val s2 = "dcda"
        val ans = checkInclusion(s1, s2)
        println(ans)
    }

}