[LintCode/LeetCode] Two Strings are Anagrams/Valid

vslam 发布于2019-08-14 15:22 / 3184人阅读

摘要：建立一个长度为的数组，统计所有个字符在出现的次数，然后减去这些字符在中出现的次数。否则，循环结束，说明所有字符在和中出现的次数一致，返回。

Program

Write a method anagram(s,t) to decide if two strings are anagrams or not.

Example

Given s="abcd", t="dcab", return true.

Challenge

O(n) time, O(1) extra space

Note

建立一个长度为256的数组，统计所有256个字符在String s出现的次数，然后减去这些字符在String t中出现的次数。若某个字符统计次数最终小于0，说明t中这个字符比s中更多，返回false。否则，循环结束，说明所有字符在s和t中出现的次数一致，返回true。

Solution

Brute Force

O(nlogn)

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] schar = s.toCharArray();
        char[] tchar = t.toCharArray();
        Arrays.sort(schar);
        Arrays.sort(tchar);
        return String.valueOf(schar).equals(String.valueOf(tchar));
    }
}

HashMap

public class Solution {
    public boolean anagram(String s, String t) {
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[(int) s.charAt(i)]++;
        }
        for (int i = 0; i < s.length(); i++) {
            count[(int) t.charAt(i)]--;
            if (count[(int) t.charAt(i)] < 0) return false;
        }
        return true;
    }
}

Slow HashMap

public class Solution {
    public boolean isAnagram(String s, String t) {
        Map map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch)+1);
            }
            else map.put(ch, 1);
        }
        for (int i = 0; i < t.length(); i++) {
            Character ch = t.charAt(i);
            if (!map.containsKey(ch)) return false;
            map.put(ch, map.get(ch)-1);
            if (map.get(ch) < 0) return false;
        }
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (map.get(ch) != 0) return false;
        }
        return true;
    }
}

Follow up: contains unicode chars?

Just give the count[] array space of 256.

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65696.html

[LintCode/LeetCode] Scramble String

摘要：首先将两个字符串化成字符数组，排序后逐位比较，确定它们等长且具有相同数量的相同字符。然后，从第一个字符开始向后遍历，判断和中以这个坐标为中点的左右两个子字符串是否满足第一步中互为的条件设分为和，分为和。 Problem Given a string s1, we may represent it as a binary tree by partitioning it to two no...

MASAILA 2019-08-14 15:45 评论0 收藏0
[LintCode/LeetCode] Two Sum

摘要：就不说了，使用的解法思路如下建立，对应该元素的值与之差，对应该元素的。然后，循环，对每个元素计算该值与之差，放入里，。如果中包含等于该元素值的值，那么说明这个元素正是中包含的对应的差值。返回二元数组，即为两个所求加数的序列。 Problem Given an array of integers, find two numbers such that they add up to a s...

xiaoxiaozi 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Add Two Numbers

Problem You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1s digit is at the head of the list. Write a f...

hedzr 2019-08-14 15:21 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate III

Problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute dif...

MageekChiu 2019-08-19 10:48 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate II

Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...

894974231 2019-08-19 10:48 评论0 收藏0