[PHP知识库]【力扣】567. 字符串的排列

目录

方法: 算是暴力遍历（PHP）

测试结果:

优化:

测试结果:

官方链接:

网上的PHP解法感觉真的很少，是我的错觉么。

方法: 算是暴力遍历（PHP）

class Solution {

    /**
     * @param String $s1
     * @param String $s2
     * @return Boolean
     */
    function checkInclusion($s1, $s2) {
        $len1 = strlen($s1);
        $len = strlen($s2);
        $arrs = str_split($s2);
        $arrs1 = str_split($s1);
        $n = $strlen = strlen($s1);

        for ($i = 0, $j = $strlen - 1; $j < $len; $i++, $j++) {
	        $arr[$i] = array_count_values(str_split(substr($s2, $i, $strlen)));
	        ksort($arr[$i]);
        }

        $resultArray1 = array_count_values($arrs1);
        ksort($resultArray1);

        foreach ($arr as $value) {
	        if ($resultArray1 === $value) {
		        return true;
	        }
        }
        return false;
    }
}

解释: 第一次循环，用子串的长度分割获得对象数组，统计数组中各个元素出现的次数，然后再按照key来升序排序，第二次循环，和子串依次对比，如果相等就 return true。

测试结果:

执行用时：1668 ms, 在所有?PHP?提交中击败了10.00%的用户

内存消耗：37.7 MB, 在所有?PHP?提交中击败了6.00%的用户

通过测试用例：106?/?106

优化:

刚提交完，发现可以优化到只用一次 for 循环即可。提高了速度。

class Solution {

    /**
     * @param String $s1
     * @param String $s2
     * @return Boolean
     */
    function checkInclusion($s1, $s2) {
        $len1 = strlen($s1);
        $len = strlen($s2);
        $arrs = str_split($s2);
        $arrs1 = str_split($s1);
        $n = $strlen = strlen($s1);

        $resultArray1 = array_count_values($arrs1);
        ksort($resultArray1);

        for ($i = 0, $j = $strlen - 1; $j < $len; $i++, $j++) {
	        $arr[$i] = array_count_values(str_split(substr($s2, $i, $strlen)));
	        ksort($arr[$i]);
            if ($resultArray1 === $arr[$i]) {
                return true;
            }
        }

        return false;
    }
}

测试结果:

执行用时：928 ms, 在所有?PHP?提交中击败了22.00%的用户

内存消耗：36.7 MB, 在所有?PHP?提交中击败了6.00%的用户

通过测试用例：106?/?106

官方链接:

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