D86 748. Shortest Completing Word
题目链接
题目分析
从给定的一个字符串中提取字符。从另一个给定的单词数组中,选择出所提取的字符在单词中出现次数相等或大于的单词。若出现次数相同,则返回第一个符合条件的单词。
假定结果必定存在。
思路
先提取字符,转换成小写,并计算字符出现的次数。
遍历数组中的每一个单词,先计算单词中每个字符出现的次数。
同时,遍历前面计算的字符出现次数,若有任何一个字符没有在当前单词中没出现,那么可以抛弃当前单词。
若出现次数小于前面计算的出现次数,也可以排除。若出现了符合的单词,先判断和原先保存的单词长度是否短。
短则覆盖,长则抛弃。最终代码
='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; }}复制代码
若觉得本文章对你有用,欢迎用资助。