[LintCode/LeetCode] Two Strings are Anagrams/Valid

vslam 發布于2019-08-14 15:22 / 3053人閱讀

摘要：建立一個長度為的數組，統計所有個字符在出現的次數，然后減去這些字符在中出現的次數。否則，循環結束，說明所有字符在和中出現的次數一致，返回。

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.

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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