Anagram 由颠倒字母顺序而构成的字
2024-10-22 22:21:47
2018-07-15 19:23:08
Valid Anagram
问题描述:
问题描述:
可以使用map来记录各个字符出现的个数,在O(n)的时间复杂度内完成,当然也可以使用排序算法在O(nlogn)完成。
public boolean isAnagram(String s, String t) {
int[] alphabet = new int[26];
for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
for (int i : alphabet) if (i != 0) return false;
return true;
}
Find All Anagrams in a String
问题描述:
问题求解:
可以使用滑动窗口在O(n)时间复杂度完成求解。
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (p.length() > s.length()) return res;
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < p.length(); i++) {
int temp = map.getOrDefault(p.charAt(i), 0);
map.put(p.charAt(i), temp + 1);
}
int begin, end, count;
begin = 0;
end = 0;
count = map.size();
for (; end < s.length(); end++) {
char c = s.charAt(end);
if (map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if (map.get(c) == 0) count--;
}
if (end - begin + 1 == p.length()) {
if (count == 0) res.add(begin);
char temp = s.charAt(begin);
if (map.containsKey(temp)) {
// 这里需要注意,必须是第一次从0转成正count++
if (map.get(temp) == 0) count++;
map.put(temp, map.get(temp) + 1);
}
begin++;
}
}
return res;
}
Group Anagrams
问题描述:
问题求解:
使用sort来判断是否为Anagram在本题中居然出奇的快,另外使用map来维护index。
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res = new ArrayList<>();
HashMap<String, Integer> map = new HashMap<>();
for (String s : strs) {
char[] temp = s.toCharArray();
Arrays.sort(temp);
String s2 = new String(temp);
if (map.containsKey(s2))
res.get(map.get(s2)).add(s);
else {
List<String> ls = new ArrayList<>();
ls.add(s);
res.add(ls);
map.put(s2, res.size() - 1);
}
}
return res;
}
最新文章
- ASP.NET MVC 插件化机制
- iOS多线程编程之NSThread的使用(转)
- php实现添加图片水印
- 文件输入流 FileInputStream类 文件输出流FileOutputStream ---转载
- 玩转无线电 -- GPS Hacking (上)
- C++ Frequently asking question
- 《通过脚本查看哪些ip被占用》shell笔记
- SQL 复杂查询
- Oracle定义常量和变量
- Away3d 骨骼动画优化
- sql server 常用小知识点
- [UWP小白日记-15]在UWP手机端实时限制Textbox的输入
- HTML5的兼容问题以及调用js文件的方法
- dede织梦数据表字段解释
- 注解ConfigurationProperties注入yml配置文件中的数据
- FICO-初级会计学
- iOS:如何实现在文字上添加拼音
- SQL Server关于WITH CUBE、WITH ROLLUP和GROUPING使用
- @RequestParam注解
- Spark的运行模式(1)--Local和Standalone