Junxian.Huang
BAN USERUse suffix tree. lengh m, n. O((m+n)n) time. O(min(m, n)^2) space
- Junxian.Huang February 23, 2013O(n) time and O(1) space is the best solution. Just keep track of the current smallest number A and currently smallest length-2 increasing piece B[0:1]. Updating it takes O(1) time.
Example: 5, 6, 1, 2, 0, 1, 0, 9.
Step 1:
A = 5, B = NULL
Step 2:
A = 5, B = [5, 6]
Step 3:
A = 1, B = [5, 6]
Step 4:
A = 1, B = [1, 2]
Step 5:
A = 0, B = [1, 2]
Step 6:
A = 0, B = [0, 1]
Step 7:
A = 0, B = [0, 1]
Step 8:
Bingo, B + 9 is length-3 increasing piece
this is not guaranteed to find a solution.
For example, dictionary = {the, there, is}.
And input is "thereis".
If you add space after "the", there is no match for the remaining "reis". You have to consider "there is"
Use trie for matching dictionary.
Recursively call when matched one word.
Depending on the dictionary, complexity varies, in the worse case, for dictionary with most similar words, such as {a, aa, aaa, aaaa, aaaaa, ...}, every char there is a recursive call and there may be 2^n possibilities. But you only need to output one solution, so the running time may not be to bad.
Whether it's top left or bottom right does not really matter, you know what I mean ...
Both min-heap and max-heap is fine, it's just two different ways to find k largest numbers. What you suggest is correct approach and I think the method I wrote original is also right. The difference is that you store the results in the heap, while I put the results outside the heap
My code is as follows, it passes LeetCode online judge.
The code can be optimized by putting more work done in recursive calls. I choose to write more code and invoke less recursive calls to save time.
The idea is to scan strings from left to right and invoke recursive calls when there is two possible cases (i.e., string a and string b has the same character).
The choice to pass string index instead of copies of substrings greatly saves time. The use of cache to store results of subproblems is key to improve performance. The running time of the given example has decreased from 15s to 0.07s on my laptop when cache is used.
//
// LeetCode_InterleavingString.cpp
// Practice
//
// Created by Junxian Huang on 2/20/13.
// Copyright (c) 2013 Junxian Huang. All rights reserved.
//
#include <iostream>
using namespace std;
short cache[1000][1000];
class Solution {
public:
string s1;
string s2;
string s3;
size_t len1;
size_t len2;
size_t len3;
bool isInterleave(string _s1, string _s2, string _s3) {
memset(cache, -1, sizeof cache);
s1 = _s1;
s2 = _s2;
s3 = _s3;
len1 = s1.length();
len2 = s2.length();
len3 = s3.length();
if (len3 != len1 + len2)
return false;
return isInter(0, 0, 0);
}
bool isInter(int l1, int l2, int l3) {
if (cache[l1][l2] >= 0) {
return cache[l1][l2];
}
while (l3 < len3) {
if (l1 == len1) {
if (s3[l3] == s2[l2]) {
l3++;
l2++;
continue;
} else {
cache[l1][l2] = 0;
return false;
}
}
if (l2 == len2) {
if (s3[l3] == s1[l1]) {
l3++;
l1++;
continue;
} else {
cache[l1][l2] = 0;
return false;
}
}
if (s1[l1] == s2[l2]) {
if (s1[l1] == s3[l3]) {
//special case
if (isInter(l1 + 1, l2, l3 + 1)) {
cache[l1][l2] = 1;
return true;
}
if (isInter(l1, l2 + 1, l3 + 1)) {
cache[l1][l2] = 1;
return true;
}
cache[l1][l2] = 0;
return false;
} else {
cache[l1][l2] = 0;
return false;
}
} else {
//not equal
if (s3[l3] == s1[l1]) {
l3++;
l1++;
} else if (s3[l3] == s2[l2]) {
l3++;
l2++;
} else {
cache[l1][l2] = 0;
return false;
}
}
}
cache[l1][l2] = 1;
return true;
}
};
/*
int main(int argc, const char *argv[]) {
Solution s;
cout << s.isInterleave("bbbbbabbbbabaababaaaabbababbaaabbabbaaabaaaaababbbababbbbbabbbbababbabaabababbbaabababababbbaaababaa", "babaaaabbababbbabbbbaabaabbaabbbbaabaaabaababaaaabaaabbaaabaaaabaabaabbbbbbbbbbbabaaabbababbabbabaab", "babbbabbbaaabbababbbbababaabbabaabaaabbbbabbbaaabbbaaaaabbbbaabbaaabababbaaaaaabababbababaababbababbbababbbbaaaabaabbabbaaaaabbabbaaaabbbaabaaabaababaababbaaabbbbbabbbbaabbabaabbbbabaaabbababbabbabbab"
) << endl;
return 0;
}//*/
The best I can think of is k*log(k).
First of all, you only need to consider the left-top k*k matrix to find the k-th largest element. It's guaranteed to be in that smaller matrix. This helps especially when k << n.
Then extract the first element of each row and put it in the max-heap with size K. Building the heap takes time k*log(k).
Then remove the max element from the heap and put the next element in the same row into the heap. This step takes k*log(k) time.
So in total, 2k*log(k) = k*log(k) time.
It only requires O(k) space.
There may be better selection algorithm with better best-case performance. If you know of a better algorithm than mine, let me know!
I'm pasting my code here for this problem.
The idea is to use merging small consecutive pieces:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Sequence {
public:
int start;
int end;
Sequence(int _start, int _end) {
start = _start;
end = _end;
}
};
class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_map<int, Sequence*> map;
for (int t = 0 ; t < num.size() ; t++) {
int i = num[t];
if (map.find(i) != map.end()) {
//found, ignore
} else {
//not found
bool f1 = (map.find(i - 1) != map.end());
bool f2 = (map.find(i + 1) != map.end());
if (f1 && f2) {
map[map[i - 1]->start]->end = map[i + 1]->end;
map[map[i + 1]->end]->start = map[i - 1]->start;
map[i] = map[map[i - 1]->start];
} else if (f1 && !f2) {
map[map[i - 1]->start]->end = i;
map[i] = new Sequence(map[i - 1]->start, i);
} else if (!f1 && f2) {
map[i] = new Sequence(i, map[i + 1]->end);
map[map[i + 1]->end]->start = i;
} else {
//!f1 && !f2
map[i] = new Sequence(i, i);
}
}
}
int max = 0;
for (auto it = map.begin() ; it != map.end() ; it++) {
if (it->second->end - it->second->start + 1 > max) {
max = it->second->end - it->second->start + 1;
}
}
return max;
}
};
/*
int main(int argc, const char* argv[]) {
Solution s;
vector<int> num;
num.push_back(100);
num.push_back(4);
num.push_back(200);
num.push_back(1);
num.push_back(3);
num.push_back(2);
cout << s.longestConsecutive(num) << endl;
return 0;
}//*/
I think DFS or BFS would work. DP would not
- Junxian.Huang February 24, 2013