algorithm/Week_02/id_13/LeetCode_242_13.java at master · feixiangcode/algorithm · GitHub

History

76 lines (69 loc) · 1.98 KB

Raw

package leetCode.week1;

import java.util.Arrays;

import java.util.HashMap;

import java.util.Map;

/**

* 有效的字母异位词

* https://leetcode-cn.com/problems/valid-anagram/

* valid-anagram：

* https://leetcode.com/problems/valid-anagram/

* @author JP.Jiang

* @version Java

* @since 2019/04/23

public class LeetCode_242_13 {

/**

* 【week2】

* 利用哈希表解决这个问题

* 遍历字符串，对读取过的单个字符进行计数

* 利用Map计数 {letter:count}

* 两个遍历后的Map进行对比

* <p>

* 时间复杂度：

* 令字符串s长度为n

* 遍历字符串 -- O(n)

* Map中计数 -- O(1)

* 总体复杂度 -- O(n)

* @param s source string

* @param t target string

* @return source equals target -> true ; else -> false

public boolean isAnagram(String s, String t) {

return countMap(s).equals(countMap(t));

}

private Map<Character, Integer> countMap(String s) {

Map<Character, Integer> countMap = new HashMap<>();

for (char ch : s.toCharArray()) {

if (!countMap.containsKey(ch)) {

countMap.put(ch, 1);

} else {

countMap.replace(ch, countMap.get(ch) + 1);

}

return countMap;

}

/**

* 【week1】

* 拿到两个字符串先排序

* 如果两个排序后的字符串相等

* 那么就是一样的

* <p>

* 时间复杂度：

* 令字符串s长度为n

* O(N*logN)

* @param s source string

* @param t target string

* @return source equals target -> true ; else -> false

public boolean isAnagramForWeek1(String s, String t) {

return sorted(s).equals(sorted(t));

}

private String sorted(String s) {

char[] ch = s.toCharArray();

Arrays.sort(ch);

return Arrays.toString(ch);

}

algorithm/Week_02/id_13/LeetCode_242_13.java at master · feixiangcode/algorithm · GitHub

Expand file tree

Breadcrumbs

LeetCode_242_13.java

Latest commit

History

Breadcrumbs

LeetCode_242_13.java

File metadata and controls