算法day07

admin2024-05-15  0

 第一题

30. 串联所有单词的子串

算法day07,第1张

class Solution
{
 public List<Integer> findSubstring(String s, String[] words) 
 {
 List<Integer> ret = new ArrayList<Integer>();
 // 保存字典中所有单词的频次
 Map<String, Integer> hash1 = new HashMap<String, Integer>(); 
 for(String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1);
 int len = words[0].length(), m = words.length;
 for(int i = 0; i < len; i++) // 执⾏次数
 {
 // 保存窗⼝内所有单词的频次
 Map<String, Integer> hash2 = new HashMap<String, Integer>(); 
 for(int left = i, right = i, count = 0; right + len <= s.length(); 
right += len)
 {
 // 进窗⼝ + 维护 count
 String in = s.substring(right, right + len);
 hash2.put(in, hash2.getOrDefault(in, 0) + 1);
 if(hash2.get(in) <= hash1.getOrDefault(in, 0)) count++; 
 // 判断
 if(right - left + 1 > len * m)
 {
 // 出窗⼝ + 维护 count
 String out = s.substring(left, left + len);
 if(hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;
 hash2.put(out, hash2.get(out) - 1);
 left += len;
 }
 // 更新结果
 if(count == m) ret.add(left);
 }
 }
 return ret;



    }
}

第二题

ps:本次的内容就到这里了,如果大家感兴趣的话就请一键三连哦!!! 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!