菜鸟的问题：Given a string, find whether it has any permutation of another string# JobHunting - 待字闺中
a*n
1 楼
恳请指教！多谢
f*t
2 楼
keyword: anagram
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
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
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
好了。
【在 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
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
6 楼
two pointer + counter O(n)
p*2
7 楼
slide window more accurate
c*a
8 楼
count一下character的frenquency就行了吧
c*t
9 楼
zkss. 你是不是考虑了顺序也要一样？题目说的是permutation啊，我只想到卖糕的O(m
+n)算法。
【在 p*****2 的大作中提到】
: two pointer + counter O(n)
+n)算法。
【在 p*****2 的大作中提到】
: two pointer + counter O(n)
p*2
10 楼
(m
O(m+n)不就是O(n)吗
【在 c********t 的大作中提到】
: zkss. 你是不是考虑了顺序也要一样？题目说的是permutation啊，我只想到卖糕的O(m
: +n)算法。
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]);
}
}
}
}
public static int GetCode(char c)
{
return c * (c ^ 23405) % 74259;
}
public static bool IsPermut(string a, string b)
{
List
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
12 楼
contains是只需要B中的character都出现了？还是连续出现呢？
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)吗
如果是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
14 楼
nice.
【在 p*****2 的大作中提到】
: slide window more accurate
【在 p*****2 的大作中提到】
: slide window more accurate
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)
c*t
16 楼
你说得对。
1)
【在 p*****2 的大作中提到】
:
: 不需要。可以用两个hashmap和一个counter降低时间复杂度。每滑一次的比较就是O(1)
: 的了。
1)
【在 p*****2 的大作中提到】
:
: 不需要。可以用两个hashmap和一个counter降低时间复杂度。每滑一次的比较就是O(1)
: 的了。
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[] set2 = new char[256];
for(int i=0;i
set2[s2.charAt(i)]++;
}
int counter=0;
for(int i =s2.length();i
set1[s1.charAt(counter++)]--;
set1[s1.charAt(i)]++;
}
if(isAnagram(set1,set2)) return true;
return false;
}
检查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[] set2 = new char[256];
for(int i=0;i
set2[s2.charAt(i)]++;
}
int counter=0;
for(int i =s2.length();i
set1[s1.charAt(counter++)]--;
set1[s1.charAt(i)]++;
}
if(isAnagram(set1,set2)) return true;
return false;
}
g*y
18 楼
举个例子
A串bacde B串cb
return false
这个应该不能用字谜来解。就是把B都hash了也要O(m*n)
A串bacde B串cb
return false
这个应该不能用字谜来解。就是把B都hash了也要O(m*n)
b*e
19 楼
Hash.
在 aubon (green) 的大作中提到: 】
在 aubon (green) 的大作中提到: 】
b*e
20 楼
If using hash, why bother sliding?
What I am missing?
在 peking2 (scala) 的大作中提到: 】
1)
What I am missing?
在 peking2 (scala) 的大作中提到: 】
1)
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; i
}
return 1;
}
/*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
}
return 1;
}
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
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
vector
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
相关阅读
[合集] 简单讲一下面试时的用餐礼仪说说昨天的Cisco onsite分享一下我找工作的经验 by datou (转载)反面教材-Google的Phone Interview经验看来要准备裸奔了……一个人力资源经理的自白 (转载)冒个泡：One Tip on Cover Letter (Email)M$的几个面试题今天的面试问题及请求建议[合集] My solution Re: 网上看到一道google面试题some of my 30m phone interview questions找工作流水账（4）LP今天ONSITE 当场得到 OFFER，总结回报（1）说一说我的看法星期五的面世比较郁闷，不知道有没有戏offer到了，+我的经验学生物、化学的同学想去药厂可以多和SAPA的专业人士交流衣带渐宽终不悔， 为伊消得人憔悴second round amazon interview我找工作的经历，PE