Leetcode PHP题解--D86 748. Shortest Completing Word

D86 748. Shortest Completing Word

题目链接

748. Shortest Completing Word

题目分析

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

假定结果必定存在。

思路

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

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

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

若出现次数小于前面计算的出现次数，也可以排除。

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

短则覆盖，长则抛弃。

最终代码

<?php
class 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)资助。