新博文地址:[leetcode]Anagrams
Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
Note: All inputs will be in lower-case.
这道题我没看懂啥意思,看了解释之后才知道是从给定的数组中挑出互为anagram的单词,这道题曾经在编程珠玑上看到过,因此没多做考虑就直接开始编码了
具体算法思想是:
对每个单词做出标记,例如对于anagram标记为a3g1m1n1r1,表示这个单词有3个a,1个g等等。
第一遍遍历数组就将所有的单词做出来标记,接下来只需要对比标记即可。
为了优化时间复杂度,在第一遍遍历时,顺便把所有具有相同标记的单词全都丢在了同一个list中。
因此时间复杂度为O(n)
具体代码如下:
public List<String> anagrams(String[] strs) { List<String> result = new ArrayList<String>(); Map<String,List<String>> map = new HashMap<String,List<String>>(); if(strs == null || strs.length == 1){ return result; } for(String s : strs){ String seq = getSequence(s); if(map.containsKey(seq)){ map.get(seq).add(s); }else{ List<String> list = new ArrayList<String>(); list.add(s); map.put(seq, list); } } for(Map.Entry<String, List<String>> entry : map.entrySet()){ if(entry.getValue().size() > 1){ for(String s : entry.getValue()){ result.add(s); } } } return result; } private String getSequence(String s){ if("".equals(s)){ return ""; } int[] hash = new int[256]; StringBuilder sb = new StringBuilder(); for(int i = 0; i < s.length(); i++){ hash[s.charAt(i)]++; } for(int i = 97; i < 123; i++){ if(hash[i] != 0){ sb.append((char)i).append(hash[i]); } } return sb.toString(); }
第一遍做的时候少考虑了空字符串,实在不应该
相关推荐
java java_leetcode题解之Group Anagrams.java
java java_leetcode题解之Find All Anagrams in a String.java
java入门 java_leetcode题解之049_Group_Anagrams
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
js js_leetcode题解之49-group-anagrams.js
c语言入门 C语言_leetcode题解之49-group-anagrams.c
c c语言_leetcode题解之0438_find_all_anagrams_in_a_string
在LeetCode上,单词接龙类问题可能表现为“Anagrams”(同字母异序词)或者“Word Ladder”(单词阶梯),这些题目要求高效地搜索满足条件的单词序列。 【压缩包子文件的文件名称列表】"LeetCode-main"可能包含了一...
- Group Anagrams: 组合所有字母异位词,即将字母顺序不同但字母组合相同的单词分组。 - Pow(X, n): 实现x的n次幂运算,需要考虑各种边界情况和性能优化。 - N-Queens / N-Queens II: 第一个问题是经典的N皇后问题,...
- **两个字符串是否互为变位词(Anagrams)**: 判断两个字符串是否包含相同数量的相同字符。 - **最长公共子串(Longest Common Substring)**: 在两个字符串中找到长度最长的相同子串。 - **字符串旋转(Rotate String)*...
### 算法刷题笔记leetcode/lintcode #### 目录 - **Preface**:简介 - **FAQ**:常见问题解答 - **Guidelines for Contributing**:贡献指南 - **Contributors**:贡献者列表 - **Part I - Basics** - **Basics ...
Anagrams in a String Pattern: two points 双指针是这样的模式:两个指针朝着左右方向移动(双指针分为同向双指针和异向双指针),直到他们有一个或是两个都满足某种条件。 使用双指针的优势:若只用一个指针,需多...
Anagrams :简单的#hashtable问题。 BalancedBinaryTree :简单的#balance #tree问题。 BestTimetoBuyandSellStock :简单的问题。 BestTimetoBuyandSellStockII :简单的问题。 BestTimetoBuyandSellStockIII : ...
groupAnagrams ( String [] strs ) { if (strs == null || strs . length == 0 ) return null ; Map< String , List< String > > map = new HashMap< String , List< String > > (); Arrays . sort(strs...
vscode安装leetcode leetcode-js-tdd leetcode 勇士的简单样板 如何使用 克隆这个 repo 在你的 vscode 中安装 配置扩展以使用 repo ...使用1.two-sum.js案例导出解决方案 ...参见49.group-anagrams.js
vscode提交leetcode 我的leetcode练习笔记 结构 代码在根路径中,每个cpp文件都是一个问题的解决方案 有关特定问题的解决方案的一些说明在目录中。 我使用的工具 我使用扩展来测试和调试本地并提交我确定我的解决...
加油站 leetcode 力码 ...anagrams(49).swift Leetcode\group 给定他们所属的组大小的人(1282).swift Leetcode\数组中的第k 个最大元素(215).swift Leetcode\最长递增子序列(300).swift Leetcode\ma
LeetCode438_Find_All_Anagrams_in_String 438题目:给定一个字符串s和一个非空字符串p,字符串全部由小写字母子组成。 在S中找出所有p对应的anagrams(颠倒)字符串的子串,返回这些子串的起始索引 如s="cbaebabacd...