Redian新闻
>
菜鸟的问题:Given a string, find whether it has any permutation of another string
avatar
菜鸟的问题:Given a string, find whether it has any permutation of another string# JobHunting - 待字闺中
a*n
1
恳请指教!多谢
avatar
f*t
2
keyword: anagram
avatar
a*n
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
avatar
t*g
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

avatar
d*g
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

avatar
p*2
6
two pointer + counter O(n)
avatar
p*2
7
slide window more accurate
avatar
c*a
8
count一下character的frenquency就行了吧
avatar
c*t
9
zkss. 你是不是考虑了顺序也要一样?题目说的是permutation啊,我只想到卖糕的O(m
+n)算法。

【在 p*****2 的大作中提到】
: two pointer + counter O(n)
avatar
p*2
10

(m
O(m+n)不就是O(n)吗

【在 c********t 的大作中提到】
: zkss. 你是不是考虑了顺序也要一样?题目说的是permutation啊,我只想到卖糕的O(m
: +n)算法。

avatar
y*n
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]);
}
}
}
}
avatar
l*i
12
contains是只需要B中的character都出现了?还是连续出现呢?
avatar
c*t
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)吗

avatar
G*A
14
nice.

【在 p*****2 的大作中提到】
: slide window more accurate
avatar
p*2
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)

avatar
c*t
16
你说得对。

1)

【在 p*****2 的大作中提到】
:
: 不需要。可以用两个hashmap和一个counter降低时间复杂度。每滑一次的比较就是O(1)
: 的了。

avatar
c*a
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;iset1[s1.charAt(i)]++;
set2[s2.charAt(i)]++;
}
int counter=0;
for(int i =s2.length();iif(isAnagram(set1,set2)) return true;
set1[s1.charAt(counter++)]--;
set1[s1.charAt(i)]++;
}
if(isAnagram(set1,set2)) return true;
return false;
}
avatar
g*y
18
举个例子
A串bacde B串cb
return false
这个应该不能用字谜来解。就是把B都hash了也要O(m*n)
avatar
b*e
19
Hash.
在 aubon (green) 的大作中提到: 】
avatar
b*e
20
If using hash, why bother sliding?
What I am missing?
在 peking2 (scala) 的大作中提到: 】
1)
avatar
d*2
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; iif(checker[t[i]] == 0) return 0;
}

return 1;
}
avatar
d*3
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
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。