a***n
发帖数: 38 | |
f*******t
发帖数: 7549 | |
a***n
发帖数: 38 | 3 谢谢，可是我的问题不完全一样，
i want to check if string A contains any permutation of string B, for
example, string A : absditg, string B: ba, then it is yes
【在 f*******t 的大作中提到】
: keyword: anagram
|
t******g
发帖数: 44 | 4 差不多把， 你sort一下，一个个比就好了， 或者，hashtable存一下，看下table就
好了。
【在 a***n 的大作中提到】
: 谢谢，可是我的问题不完全一样，
: i want to check if string A contains any permutation of string B, for
: example, string A : absditg, string B: ba, then it is yes
|
d*********g
发帖数: 154 | 5
这样做不知对不对：看A里面是否有一个substring A_sub，使得A_sub里出现的每个字
符都在B里出现过，并且出现的次数一样。如果找到这样的A_sub，就return yes。
【在 a***n 的大作中提到】
: 谢谢，可是我的问题不完全一样，
: i want to check if string A contains any permutation of string B, for
: example, string A : absditg, string B: ba, then it is yes
|
p*****2
发帖数: 21240 | 6 two pointer + counter O(n) |
p*****2
发帖数: 21240 | 7 slide window more accurate |
c*****a
发帖数: 808 | 8 count一下character的frenquency就行了吧 |
c********t
发帖数: 5706 | 9 zkss. 你是不是考虑了顺序也要一样？题目说的是permutation啊，我只想到卖糕的O(m
+n)算法。
【在 p*****2 的大作中提到】
: two pointer + counter O(n)
|
p*****2
发帖数: 21240 | 10
(m
O(m+n)不就是O(n)吗
【在 c********t 的大作中提到】
: zkss. 你是不是考虑了顺序也要一样？题目说的是permutation啊，我只想到卖糕的O(m
: +n)算法。
|
|
|
y****n
发帖数: 743 | 11 我的方法：通过一个顺序无关的校验码，找到“疑似”字串，在对“疑似”进行甄别。
public static int GetCode(char c)
{
return c * (c ^ 23405) % 74259;
}
public static bool IsPermut(string a, string b)
{
List chars = new List(a.ToArray());
foreach (char ch in b)
if (chars.Contains(ch))
chars.Remove(ch);
else
return false;
return true;
}
public static void FindPermut(string a, string b)
{
if (a.Length >= b.Length)
{
int codeSumB = 0;
for (int i = 0; i < b.Length; i++)
codeSumB += GetCode(b[i]);
int codeSumA = 0;
for (int i = 0; i < a.Length; i++)
{
codeSumA += GetCode(a[i]);
if (i >= b.Length - 1)
{
if (codeSumA == codeSumB)
{
string candidate = a.Substring(i - b.Length + 1, b.Length);
if (IsPermut(candidate, b))
Console.WriteLine("Start:{0}\t{1}", i - b.Length + 1, candidate);
}
codeSumA -= GetCode(a[i - b.Length + 1]);
}
}
}
} |
l****i
发帖数: 396 | 12 contains是只需要B中的character都出现了？还是连续出现呢？ |
c********t
发帖数: 5706 | 13 二爷，我敲错了，是O(m*n) n: a.length m: b.length
如果是slide windows一个个划过去,比较a.substring(i, i+b.length())与b是O(m*n)
复杂度，除非有类似KMP的解法才有可能降为O(n)
【在 p*****2 的大作中提到】
:
: (m
: O(m+n)不就是O(n)吗
|
G****A
发帖数: 4160 | 14 nice.
【在 p*****2 的大作中提到】
: slide window more accurate
|
p*****2
发帖数: 21240 | 15
不需要。可以用两个hashmap和一个counter降低时间复杂度。每滑一次的比较就是O(1)
的了。
【在 c********t 的大作中提到】
: 二爷，我敲错了，是O(m*n) n: a.length m: b.length
: 如果是slide windows一个个划过去,比较a.substring(i, i+b.length())与b是O(m*n)
: 复杂度，除非有类似KMP的解法才有可能降为O(n)
|
c********t
发帖数: 5706 | 16 你说得对。
1)
【在 p*****2 的大作中提到】
:
: 不需要。可以用两个hashmap和一个counter降低时间复杂度。每滑一次的比较就是O(1)
: 的了。
|
c*****a
发帖数: 808 | 17 char[256] set + 2个指针
检查isAnagram用constant time 256，就是O(1)
总共就是O(n) time, O(1) space， 256space是constant...
public boolean isAnagram(char[]s1,char[]s2){
int i=0;
for(char c:s1)
if(c!=s2[i++]) return false;
return true;
}
public boolean checkAna(String s1,String s2){
if(s1==null || s2==null)return false;
if(s2.length()==0) return true;
if(s1.length()
char[] set1 = new char[256];
char[] set2 = new char[256];
for(int i=0;i
set1[s1.charAt(i)]++;
set2[s2.charAt(i)]++;
}
int counter=0;
for(int i =s2.length();i
if(isAnagram(set1,set2)) return true;
set1[s1.charAt(counter++)]--;
set1[s1.charAt(i)]++;
}
if(isAnagram(set1,set2)) return true;
return false;
} |
g****y
发帖数: 2810 | 18 举个例子
A串bacde B串cb
return false
这个应该不能用字谜来解。就是把B都hash了也要O(m*n) |
b*******e
发帖数: 217 | 19 Hash.
在 aubon (green) 的大作中提到: 】 |
b*******e
发帖数: 217 | 20 If using hash, why bother sliding?
What I am missing?
在 peking2 (scala) 的大作中提到: 】
1) |
d**********2
发帖数: 52 | 21 这个貌似比较简单吧。。
/*return 1 if s is anagram of t, otherwise return 0*/
int anagram(char s[], char t[]){
int checker[256];
int i;
memset(checker, 0, sizeof(checker));
for(i=0; i< sizeof(s)/sizeof(char), i++;){
checker[s[i]] ++;
}
for(i=0; i
if(checker[t[i]] == 0) return 0;
}
return 1;
} |
d*******3
发帖数: 58 | 22 @dingdang2012,你这个不对，LZ的题意是S中是否存在一个子串是T的一个permutation,
garphy的例子：
S串bacde T串cb，应该返回false,你的代码返回true了。
peking2 的两个hashmap+一个counter是正解，时间复杂度O(m+n)
我献丑贴下代码：
bool HasPermuateSubstr(string& S,string& T)
{
int n = S.length();
int m = T.length();
if( n < m || m <=0)return false;
vector findCount(256,0);
vector needCount(256,0);
for(int i = 0;i < m;i++)needCount[T[i]]++;
//initilize the window
int findLen=0;
for(int i = 0;i < m;i++)
{
findCount[S[i]]++;
if(findCount[S[i]] <= needCount[S[i]])findLen++;
}
if(findLen == m)return true;
//slide the window
for(int start = 1;start <= n-m;start++)
{
findCount[S[start-1]]--;
if(findCount[S[start-1]] < needCount[S[start-1]])
findLen--;
findCount[S[start+m-1]]++;
if(findCount[S[start+m-1] < needCount[S[start+m-1])
findLen++;
if(findLen == m)return true;
}
return false;
}
简单测了下，不知道有木有bug...
test case:
a dfdfd false
abc b true
aaaaa aaa true
agdddzwx dd true
abceeff ece true
dabcdefg ab true
abcdef ce false
bacde cb false
abbceedf bbe false
abcedfghijklmno mlkjihgfdec true
【在 d**********2 的大作中提到】
: 这个貌似比较简单吧。。
: /*return 1 if s is anagram of t, otherwise return 0*/
: int anagram(char s[], char t[]){
: int checker[256];
: int i;
: memset(checker, 0, sizeof(checker));
: for(i=0; i< sizeof(s)/sizeof(char), i++;){
: checker[s[i]] ++;
: }
: for(i=0; i
|
