Longest Palindrome Substring - Leet Code Solution
Problem Statement Given a string s, find the longest palindromic substring in s…
September 10, 2020
Given two strings s and t , write a function to determine if t is an anagram of s.
Example
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
Note: You may assume the string contains only lowercase alphabets.
First try to understand what an Anagram is. Its NOT about checking order of characters in a string.
Its about checking that:
A simple solution can be to sort the strings first, then compare.
public boolean isAnagram_sort(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] s1 = s.toCharArray();
char[] s2 = t.toCharArray();
Arrays.sort(s1);
Arrays.sort(s2);
return Arrays.equals(s1, s2);
}
It is equal to complexity taken by sorting.
Its O(nlogn)
Another simple solution is that we can use a HashMap<Character, Integer>
.
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i=0; i<s.length(); i++) {
int count = map.getOrDefault(s.charAt(i), 0);
count ++;
map.put(s.charAt(i), count);
}
for (int i=0; i<t.length(); i++) {
int count = map.getOrDefault(t.charAt(i), 0);
if (count == 0) {
return false;
}
count --;
map.put(t.charAt(i), count);
}
return true;
}
Its O(n)
Since we know that there are only lowercase characters
. We know the unique number of characters will be 26
.
Integer array
of count 26
a
, second to b
and so on.public boolean isAnagram_array(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int count[] = new int[26];
for (int i=0; i<s.length(); i++) {
count[s.charAt(i) - 'a'] ++;
}
for (int i=0; i<t.length(); i++) {
if (count[t.charAt(i) - 'a'] <= 0) {
return false;
}
count[t.charAt(i) - 'a'] --;
}
return true;
}
Note that t.charAt(i) - 'a'
is just to manipulate our indexes.
Its O(n)
Problem Statement Given a string s, find the longest palindromic substring in s…
Problem Statement Given a non-empty array of digits representing a non-negative…
Problem Statement Determine whether an integer is a palindrome. An integer is a…
Problem Statement Given an array nums of n integers, are there elements a, b, c…
Problem Statement Given a string, find the first non-repeating character in it…
Problem Implement an algorithm to determine if a string has all the characters…
Introduction This post has the complete code to send email through smtp server…
Introduction In a normal email sending code from python, I’m getting following…
Introduction In one of my app, I was using to talk to . I have used some event…
Introduction So you have a Django project, and want to run it using docker image…
Introduction It is very important to introduce few process so that your code and…
Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…