n********y
发帖数: 312 | 1 一个面试官问了一个问题剩下15分钟，就叫我问问题了。
脑袋短路了，COMMUNICATION有问题。 问我数学题目，我写CODE了.
其他题目还好，不难。有点意思的是
check whether any anagram of string S is substring of T. |
f*****e
发帖数: 2992 | 2 # of characters('a' to 'z') of T >= # of characters('a' to 'z') of S ?
【在 n********y 的大作中提到】
: 一个面试官问了一个问题剩下15分钟，就叫我问问题了。
: 脑袋短路了，COMMUNICATION有问题。 问我数学题目，我写CODE了.
: 其他题目还好，不难。有点意思的是
: check whether any anagram of string S is substring of T.
|
x****g
发帖数: 1512 | 3 这个不行吧，S中的无视位置，但T有。要在T中连续，呵呵。
第一感觉应该是那个O(N)的算法。
2个下标的那个方法，找最短覆盖，本题要求最小短覆盖等于S。
【在 f*****e 的大作中提到】
: # of characters('a' to 'z') of T >= # of characters('a' to 'z') of S ?
|
s*******z
发帖数: 83 | |
G**C
发帖数: 365 | 5 no need. this is different and easier.
【在 s*******z 的大作中提到】
: 支持楼上正解, 最小窗口覆盖
|
s*******z
发帖数: 83 | 6 可能说法不一样: 不是维持一个窗口, 前后坐标移动, 找一个长度为len(S)的
substring吗?
当然, 这里移动的时候, 前后坐标一起移动.
还能在简化吗? |
x****g
发帖数: 1512 | 7 加速可以的，比如遇见s里没的前后标都直接跳到下一个，但O(N)性质不变。
【在 s*******z 的大作中提到】
: 可能说法不一样: 不是维持一个窗口, 前后坐标移动, 找一个长度为len(S)的
: substring吗?
: 当然, 这里移动的时候, 前后坐标一起移动.
: 还能在简化吗?
|
A*********c
发帖数: 430 | 8 How about对query建个freq数组，然后记录频率开扫。
如果发现断档了重置频率，跳到i+1继续。
扫超了跳到重复字符下标＋1继续，途中重置频率。
和min win substr一个意思，O(n).
此那一无算法可否一战？
【在 n********y 的大作中提到】
: 一个面试官问了一个问题剩下15分钟，就叫我问问题了。
: 脑袋短路了，COMMUNICATION有问题。 问我数学题目，我写CODE了.
: 其他题目还好，不难。有点意思的是
: check whether any anagram of string S is substring of T.
|
s********x
发帖数: 914 | 9 // check if string a can be the anagram of substring of b
public static boolean isAnagramSubstring(String a, String b) {
if (a == null || a.length() == 0 || b == null) {
throw new IllegalArgumentException();
}
if (a.length() > b.length()) {
return false;
}
int size = a.length();
Map needToFind = new HashMap
(size);
for (int i = 0; i < size; i++) {
char c = a.charAt(i);
needToFind.put(c, needToFind.containsKey(c) ? needToFind.get(c)
+ 1 : 1);
}
int count = 0;
for (int i = 0; i < size; i++) {
// iterate through b
char c = b.charAt(i);
Integer num = needToFind.get(c);
if (num != null) {
if (num > 0) {
count++;
}
needToFind.put(c, num - 1);
}
}
if (count == size) {
return true;
}
for (int end = size; end < b.length(); end++) {
int beg = end - size;
char c = b.charAt(beg);
Integer num = needToFind.get(c);
if (num != null) {
if (num >= 0) {
count--;
}
needToFind.put(c, num + 1);
}
c = b.charAt(end);
num = needToFind.get(c);
if (num != null) {
if (num > 0) {
count++;
}
needToFind.put(c, num - 1);
}
if (count == size) {
return true;
}
}
return false;
}
【在 n********y 的大作中提到】
: 一个面试官问了一个问题剩下15分钟，就叫我问问题了。
: 脑袋短路了，COMMUNICATION有问题。 问我数学题目，我写CODE了.
: 其他题目还好，不难。有点意思的是
: check whether any anagram of string S is substring of T.
|
c****m
发帖数: 855 | 10 有个 google 说面经的网站 说有人不会用 grep。写了个2000行的代码 找出一串中的
什么数字。
【在 s********x 的大作中提到】
: // check if string a can be the anagram of substring of b
: public static boolean isAnagramSubstring(String a, String b) {
: if (a == null || a.length() == 0 || b == null) {
: throw new IllegalArgumentException();
: }
:
: if (a.length() > b.length()) {
: return false;
: }
:
|
g*****g
发帖数: 212 | 11 bool isAnagramSubstring(string a, string b)
{
int n = a.length();
int m = b.length();
unordered_map fmap;
unordered_map cmap;
for(int i=0; i
{
int c = 1;
if (fmap.find(b[i]) != fmap.end())
{
c += fmap[b[i]];
}
fmap[b[i]] = c;
cmap[b[i]] = 0;
}
int cnt = 0;
int j = -1;
for(int i=0; i
{
char c = a[i];
if (cmap.find(c) == cmap.end() || cmap[c] == fmap[c])
{
for(;a[j+1] != c;j++)
{
cmap[a[j+1]] --;
cnt --;
}
j++;
}
else
{
cnt++;
cmap[c]++;
if (cnt == m)
return true;
}
}
return false;
} |
