D86 748. Shortest Completing Word

题目链接

748. Shortest Completing Word

题目分析

从给定的一个字符串中提取字符。从另一个给定的单词数组中，选择出所提取的字符在单词中出现次数相等或大于的单词。若出现次数相同，则返回第一个符合条件的单词。

假定结果必定存在。

思路

先提取字符，转换成小写，并计算字符出现的次数。

遍历数组中的每一个单词，先计算单词中每个字符出现的次数。

同时，遍历前面计算的字符出现次数，若有任何一个字符没有在当前单词中没出现，那么可以抛弃当前单词。
若出现次数小于前面计算的出现次数，也可以排除。

若出现了符合的单词，先判断和原先保存的单词长度是否短。
短则覆盖，长则抛弃。

最终代码

<?phpclass Solution {    /**         * @param String $licensePlate              * @param String[] $words                   * @return String                        */                            function shortestCompletingWord($licensePlate, $words) {                                    $plateCounts = [];                                            $licenseArray = str_split(strtolower($licensePlate));                                                    foreach($licenseArray as $val){                                                                if(($val>='a' && $val<='z')||($val>='A' && $val<='Z')){                                                                                if(!isset($plateCounts[$val])){                                                                                                    $plateCounts[$val] = 0;                                                                                                                    }                                                                                                                                    $plateCounts[$val] += 1;                                                                                                                                                }                                                                                                                                                        };                                                                                                                                                                $match = null;                                                                                                                                                                            foreach($words as $word){                                                                                                                                                                                    $wordCounts = array_count_values(str_split($word));                                                                                                                                                                                            $failed = false;                                                                                                                                                                                                    foreach($plateCounts as $char => $amount){                                                                                                                                                                                                                if(!isset($wordCounts[$char])){                                                                                                                                                                                                                                $failed = true;                                                                                                                                                                                                                                                break;                                                                                                                                                                                                                                                            }                                                                                                                                                                                                                                                                        if($amount > $wordCounts[$char]){                                                                                                                                                                                                                                                                                        $failed = true;                                                                                                                                                                                                                                                                                                        break;                                                                                                                                                                                                                                                                                                                    }                                                                                                                                                                                                                                                                                                                            }                                                                                                                                                                                                                                                                                                                                    if(!$failed){                                                                                                                                                                                                                                                                                                                                                if(is_null($match)){                                                                                                                                                                                                                                                                                                                                                                $match = $word;                                                                                                                                                                                                                                                                                                                                                                            }                                                                                                                                                                                                                                                                                                                                                                                        else{                                                                                                                                                                                                                                                                                                                                                                                                        if(strlen($match)>strlen($word)){                                                                                                                                                                                                                                                                                                                                                                                                                            $match = $word;                                                                                                                                                                                                                                                                                                                                                                                                                                            }                                                                                                                                                                                                                                                                                                                                                                                                                                                        }                                                                                                                                                                                                                                                                                                                                                                                                                                                                }                                                                                                                                                                                                                                                                                                                                                                                                                                                                    }                                                                                                                                                                                                                                                                                                                                                                                                                                                                            return $match;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。