phpstudy集成环境

 首页 > php 判断一个字符串中的字符是否都在另一个中出现(算法)

php 判断一个字符串中的字符是否都在另一个中出现(算法)

假设这有一个各种字母组成的字符串A，假设这还有另外一个字符串B。 从算法上讲，什么方法能最快的查出所有字符串A里的字母在字符串B里都有？

为什么我尝试了楼上几位贴出来的方法怎么都不是楼主想要的答案？
菜鸟在这贴个供大家喷的代码段 

<?php
$a = 'aGasdjhyzxhjkASDqudhaTskjbFjlhicikgckzjhcjlasdyioyqweHyfhdspvuchvxcvnmaASDasydkasaSD';
$b = 'asdhnbvdhaSlsdhFDasTdhjkaAFsdhagdmnasdbasgdkasjdjagDfjagfhgzfhghzxjcjkahdajsgdGSkahd';

$a = str_split ( $a );
$b = str_split ( $b );
$c = array_flip ( $b );

$res = array ();
foreach ( $a as $index => $v ) {
    if (empty ( $b [$c [$v]] ))
        continue;
    $res [] = $b [$c [$v]];
}

print_r ( array_unique ( $res ) );

假设字符串都是小写字母吧，大小写混合的思路是一样的 1.创建一个26的元素的bool型数组array 2.对字符串B进行一遍扫描，array[B[i]-'a'] = 1,即把字符串B中出现的字母都映射到26个字母表的array数组中 3.对字符串A进行一遍扫描，如果array[A[i] - 'a'] == 1,那么说明A[i]在字符串B中有，array[A[i] - 'a'] == 0，则说明A[i]在字符串B中没有

时间复杂度O(strlen(A) + strlen(B)),不知道是否可以接受？

以前看到过一个算法 大概是这样的把每个字符串中每个字符分别赋一个数 然后把两个字符串中的数相乘 之后在用两个结果相除 如果没有余数则证明A全在B中

为什么我觉得这就是两次循环

array_diff

count( array_unique( str_split( $a ) ) ) == count( array_unique( str_split( $a.$b ) ) )

判断一个字符串中的字符是否都在另一个中出现(算法) 我怎么感觉这个不要去硬用循环吧 比如楼上的 $a = 'aGasdjhyzxhjkASDqudhaTskjbFjlhicikgckzjhcjlasdyioyqweHyfhdspvuchvxcvnmaASDasydkasaSD'; $b = 'asdhnbvdhaSlsdhFDasTdhjkaAFsdhagdmnasdbasgdkasjdjagDfjagfhgzfhghzxjcjkahdajsgdGSkahd'; 这里好像是说判断 怎么搞成了查找？ 如果是判断 完全可以用 echo strreplace(strsplit($b),'',$a)==''?'都有':'不是都有';

平衡各种需求后的答案，PCRE 实现，简单通用。嫌效率不够的话可以去掉“u”修饰符（强制 UTF-8）。

<?php
function charsissubset($h, $n) {
    return preg_match('/[^' . preg_quote($h) . ']/u', $n) ? 0 : 1;
}

echo charsissubset('abcddcba', 'abcde'); // false
echo charsissubset('abcddcba', 'abcd'); // true
echo charsissubset('abcddcba', 'badc'); // true
echo charsissubset('汉字', '字'); // true
echo charsissubset('汉字', '漢字'); // false

楼上答案的效率基本上是可以的 ... 不过还有一些优化的空间 ... 如下 ...

<?php
$check_if_all_exist = function( $a, $b ) {

    /* most effective way to traverse a string ... */
    foreach( array_unique( str_split( $a ) ) as $a_single )

        /* stop searching if we meet something not exists in $b ... */
        if ( false === strpos( $b, $a_single ) ) 

            /* all passes ..? */
            return false; return true;

};

仅限原字符串只有字母数字的情况 ... 宽字符集的话会出错 ...

效率方面 ... str_split() 和 array_unique() 这个组合完全没有问题 ...

这比一次 strlen() 之后循环执行 substr() 效率要高很多 ... 这也是我能想到的效率最高的方式 ...

至于为什么没有在最后进行一次性 array_diff() 比较只是因为没有必要 ...

我们只是想知道 是否 字符串 A 里面的元素在 字符串 B 里都有 ... 而不是都有 哪些 重复 ...

一旦 字符串 A 里面出现了 字符串 B 里面没有的元素立即停止就好 ...

我写了几个 testcase ... 最佳的情况是 $a 和 $b 都非常长 ... 我的算法效率大概是楼上算法的 1330% ...

平常情况也会快 20% - 50% 不等 ... 并且楼上三行代码我也是三行 ... code 长度相差也不会很多 ...

想来想去也想不到什么效率更高的方法了 ... 恩恩 ... 就是这样啦 ...

function check_if_all_exist($a, $b) {
    $a_as_array = array_unique(str_split($a));
    $b_as_array = array_unique(str_split($b));
    return count(array_diff($a_as_array, $b_as_array)) <= 0;
}

这么写code比较短，执行效率怎么样就不得而知了

【热门文章】
【热门文章】