Given two strings, determine if they are anagrams.


  • 2
    S
    class Solution {
    public:
        bool anagrams(string& str1, string& str2) {
            if(str1.size() != str2.size())
               return false;
    
            //record the alphabet numbers of the str1
            unordered_map<int, int>  alp2num;
            for(int i = 0; i < str1.size(); i++){
                 alp2num[str1[i]]++;
            }
            //judge if str1 and str2 are anagrams
            for(int i = 0; i < str2.size(); i++){
                 if(--alp2num[str2[i]] < 0)
                    return false;
            }
            return true;
        }
    };

  • 1
    W

    I think this code is very well and it looks so simple


  • 0
    W

    it is very good


  • 0

    Get 3 methods :

    // 直接利用桟,把所有的结点都压进去然后在出来的时候进行判断。
    	// 时间复杂度是O(N)
    	public static boolean isPalindrome1(Node head) {
    		Stack<Node> stack = new Stack<Node>();
    		Node current = head;
    		while (current != null) {
    			stack.push(current);
    			current = current.next;
    		}
    		while (head != null) {
    			if (head.value != stack.pop().value) {
    				return false;
    			}
    			head = head.next;
    		}
    		return true;
    	}
    
    	// 利用桟,但是只把右边一部分结点推进去,然后和左边进行比较,有不同就返回false
    	public static boolean isPalindrome2(Node head) {
    		// 特殊情况的处理
    		if (head == null || head.next == null) {
    			return true;
    		}
    		// 确定右子区的开始结点right
    		Node right = head.next;
    		Node current = head;
    		while (current.next != null && current.next.next != null) {
    			right = right.next;
    			current = current.next.next;
    		}
    		// 将右子区推入桟
    		Stack<Node> stack = new Stack<Node>();
    		while (right != null) {
    			stack.push(right);
    			right = right.next;
    		}
    		// 将右子区推出桟并且与左子区进行比较
    		while (!stack.isEmpty()) {
    			if (head.value != stack.pop().value) {
    				return false;
    			}
    			head = head.next;
    		}
    		return true;
    	}
    
    	public static boolean isPalindrome3(Node head) {
    		// 特殊处理
    		if (head == null || head.next == null) {
    			return true;
    		}
    		// 找出中间节点
    		Node mid = head;
    		Node current = head;
    		while (current.next != null && current.next.next != null) {
    			mid = mid.next;
    			current = current.next.next;
    		}
    		// 中间节点不再指向右边区域
    		Node right = mid.next;
    		mid.next = null;
    		Node pre = mid;
    		Node next = null;
    		// 将右子区域反转
    		while (right != null) {
    			next = right.next;
    			right.next = pre;
    			pre = right;
    			right = next;
    		}
    		right = pre;
    		// 此时pre是右子区的头结点
    		// 将左右子区域进行比较
    		boolean result = true;
    		Node left = head;
    		while (left != null && right != null) {
    			if (left.value != right.value) {
    				result = false;
    				break;
    			}
    			left = left.next;
    			right = right.next;
    		}
    		// 将右子区域进行恢复,此时left,right都在mid.next=null
    		right = pre;
    		pre = null;
    		while (right != null) {
    			next = right.next;
    			right.next = pre;
    			pre = right;
    			right = next;
    		}
    		mid.next = pre;
    		// 返回结果
    		return result;
    	}
    

  • 0
    L

    An anagram is essetially another variant of the same string with a rearrangement of the same set of characters. For example "hello" and "olehl" are anagrams. So keeping this in mind, the algorithm is to just ensure that the same letters occur exactly the same number of times. If the string contains ascii-only characters, it is fairly easy to use an integer array of size 127 to keep a count of each characters. Using a hashmap should be preferred when the letters may not be ascii. So the code for that will be:

    public boolean isAnagram(String s1, String s2)
      {
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
          return false;
        }
        int[] arr = new int[127];
        for (int i = 0; i < s1.length(); i++){
          arr[s1.charAt(i)]++;
          arr[s2.charAt(i)]--;
        }
        // All should be 0 at the end.
        return Arrays.stream(arr).filter((x) -> x != 0).count() == 0;
      }
    

  • 0

    @labs Thx! Oh, god I thought it's a question about palindrome ! thx a lot to point out !


  • 0

    Count the letters in each.

    def solve(A, B):
        count = [0] * 256
        for c in A:
            count[ord(c)] += 1
        for c in B:
            count[ord(c)] -= 1
        return not any(count)
    

  • 0
    L

    @awice This is good too. However, it should also come with the warning about the extended ascii only.


  • 0
    B

    So again one-liner, simple code for python using Counter in standard python library.

        def isAnagram(self,a,b):
            print collections.Counter(a)==collections.Counter(b)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.