Skip to content

Instantly share code, notes, and snippets.

@adohe-zz
Last active August 29, 2015 13:56
Show Gist options
  • Select an option

  • Save adohe-zz/9086729 to your computer and use it in GitHub Desktop.

Select an option

Save adohe-zz/9086729 to your computer and use it in GitHub Desktop.
string contain problem
public final class Art {
private static void checkRange(String s1, String s2) {
if(s1 == null || s2 == null)
throw new NullPointerException("null");
if(s1.length() == 0 || s2.length() == 0)
throw new IllegalArgumentException("zero");
if(s1.length < s2.length())
throw new IllegalArgumentException("length error");
}
public boolean compare(String s1, String s2) {
checkRange(s1, s2);
for(int i = 0; i < s2.length(); i++) {
int j;
for(j = 0; (j < s1.length()) && (s1.charAt(j) != s2.charAt(i)); ++j)
;
if(j == s1.length())
return false;
}
return true;
}
public boolean compareTwo(String s1, String s2) {
checkRange(s1, s2);
int[] array = new int[26];
for(int i = 0; i < s1.length(); i++) {
++array[s1.charAt(i) - 'A'];
}
for(int j = 0; j < s2.length(); j++) {
if(array[s2.charAt(j) - 'A'] == 0)
return false;
}
return true;
}
public boolean compareThree(String s1, String s2) {
checkRange(s1, s2);
int[] array = new int[26];
int m = 0;
for(int i = 0; i < s2.length(); i++) {
if(array[s2.charAt(i) - 'A'] == 0) {
array[s2.charAt(i) - 'A'] = 1;
++m;
}
}
for(int j = 0; j < s1.length(); j++) {
if(array[s1.charAt(j) - 'A'] == 1) {
array[s1.charAt(j) - 'A'] = 0;
--m;
}
}
return m == 0;
}
//Maybe the best solution
//the time complexity is O(m+n)
//the space complexity is O(1)
public boolean compareFour(String s1, String s2) {
checkRange(s1, s2);
int hash = 0;
for(int i = 0; i < s1.length(); i++) {
hash |= (1<<(s1.charAt(i) - 'A'))
}
for(int i = 0; i < s2.length(); i++) {
if((hash & (s2.charAt(i) - 'A')) == 0) {
return false;
}
}
return true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment