just_passing_through
BAN USERwith no condition on 'c' would not the max len for the generated string be infinity? (baacaacaac.....aacaacccccccccccccccccccccccccc...)
- just_passing_through March 28, 2012Seems like you're building words for dial sequence '23456789', no? The original problem statement says "you're given a number" (dial sequence), which could be of various length.
I have the following code for this problem:
char pad[][5] = {" ", " ", "abc","def","ghi","jkl","mno", "pqrs", "tuv", "wxyz"};
size_t button_size(size_t button_num) {
return strlen(pad[button_num]);
}
char button_char(size_t button_num, size_t char_num) {
return pad[button_num][char_num];
}
void build_word(const size_t curr_pos, const string& dial_seq, string str) {
if(curr_pos == dial_seq.length()) {
cout << str << endl;
} else {
for(size_t i = 0; i < button_size(dial_seq[curr_pos] - '0'); ++i) {
build_word(curr_pos + 1, dial_seq, str + button_char(dial_seq[curr_pos] - '0', i));
}
}
}
build_word(0, dial_seq, "");
Yep, I mentioned the corner cases (M==0, N==0) originally. They're being checked and handled outside of the function main loop:
if(head == NULL) {
cerr << "try again" << endl;
exit(1);
}
if(N == 0) // nothing to delete
return head;
List *h = head;
if(M == 0) {
// delete the whole list
while(h) {
List *tmp = h;
h = h->next;
delete tmp;
}
return NULL;
}
You're right! Thanks for being thorough :). So I failed to come up with an algorithm with a 'decent' complexity, all I can think of now is extending raj's (see above) approach for all possible substrings really. (The code example below does not work for strings with repetitive chars, please see raj's code for how to streamline this (trivial)).
struct consec_substr {
char const *start;
size_t len;
consec_substr(char const * const start_, size_t const len_) : start(start_), len(len_) {}
};
void update_results_if_better(consec_substr &final_result, const consec_substr& curr_result) {
if(curr_result.len > final_result.len) {
final_result = curr_result;
}
}
void find_consec_substring2(char const * const str) {
const size_t len = strlen(str);
consec_substr final_result(str, 0);
for(size_t start = 0; start < len - 1; ++start) {
// if remaining substring is smaller than the result already obtained, no need to look further
if(len - start <= final_result.len) break;
for(size_t end = len; end > start; --end) {
unsigned char maxC = str[start], minC = str[start];
for(size_t i = start; i < end; ++i) {
if(str[i] > maxC) maxC = str[i];
if(str[i] < minC) minC = str[i];
}
if(maxC - minC == end - start - 1) {
update_results_if_better(final_result, consec_substr(str + start, end - start));
break;
}
}
}
cout << string(str) << " - " << string(final_result.start, final_result.start + final_result.len) << endl;
}
int main() {
char str[] = "dabcfeightv";
char str2[] = "abefijcdgh";
char str3[] = "bdcapfgehikjvml";
char str4[] = "dbapclemfojnhkig";
char str5[] = "clebajnkd";
find_consec_substring2(str);
find_consec_substring2(str2);
find_consec_substring2(str3);
find_consec_substring2(str4);
find_consec_substring2(str5);
return 0;
}
Hi, too many variables and too many checks, I think there's a simpler way to implement this. And also you're forgetting to check M==0 and N==0 corner cases, which simplify the whole thing noticably.
size_t count = 0;
List *retain_finish;
while(h != NULL) {
if(count < M) {
if(count == M - 1) retain_finish = h;
h = h->next;
++count;
} else {
List *tmp = h;
h = h->next;
delete tmp;
retain_finish->next = h;
count = count == M + N - 1 ? 0 : count + 1;
}
}
sure, the idea is simple really, you go through the string and you keep track of all substrings, that appear to be consisting of consecutive symbols. For example, say we have string "dabccdfeightdghiv". The algorithm first goes and builds a set of subranges (substrings, that have consecutive characters). So the string "dabccdfeightdghiv" is divided into "d", "abc", "cd", "fe", "i", "gh", "t", "d", "ghi", "v". Now that we have those substrings as subranges we know the min and max character for each substring and we can check if neighboring subranges could be joined. So we go through list of "d", "abc", "cd", "fe", "i", "gh", "t", "d", "ghi", "v" and we join the subranges that would represent a consecutive string. And the list would transform into "dabc", "cdef", "igh", "t", "d", "ghi", "v" and we continue joining neigboring subranges until there's at least one pair that could be joined. This is how you eventually arrive to "cdef" joining with "igh". That's the last pair to be joined, so the process stops after that and the last step is just going through the list of subranges in order to find one with maximum length. Looks plausible?
- just_passing_through March 23, 2012Here's what I got. Does not rely on characters uniqueness as well:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class substr_range {
char b, e;
size_t idx;
public:
substr_range(char c, size_t idx_) : b(c), e(c), idx(idx_) {}
// returns true, if char was added and false if new range needs to be created
bool add_char(char c) {
if(c == b - 1) {
b = c;
return true;
} else if(c == e + 1) {
e = c;
return true;
} else {
return false;
}
}
// returns true, if two substring ranges were joined and false otherwise
// the first substring range will have it's range updated and the second one can be ignored
bool join(const substr_range& other) {
if(other.b == e + 1) {
e = other.e;
return true;
} else if(other.e == b - 1) {
b = other.b;
return true;
} else {
return false;
}
}
size_t index() const {return idx;}
size_t len() const {return e - b + 1;}
};
int main() {
char str[] = "dabccdfeightdghiv", *s = str;
vector<substr_range> ranges(1, substr_range(*s, 0));
while(*(++s)) {
if(!ranges.back().add_char(*s)) {
ranges.push_back(substr_range(*s, s - str));
}
}
if(ranges.size() == 1) {
cout << "hooray, the string's characters are all consecutive" << str;
return 0;
}
bool joined = false;
do {
joined = false;
for(auto i = begin(ranges); i < end(ranges) - 1; ++i) {
if(i->join(*(i + 1))) {
ranges.erase(i + 1);
joined = true;
}
}
} while(joined);
auto i = begin(ranges);
size_t maxlen(i->len()), idx(i->index());
++i;
for(; i < end(ranges); ++i) {
if(i->len() > maxlen) {
maxlen = i->len();
idx = i->index();
}
}
cout << "found a substring with " << maxlen << " consecutive characters" << endl
<< "the substring is " << string(str + idx, str + idx + maxlen) << endl;
return 0;
}
Hi, I'm not sure this implementation will find 'acb' in, say 'sacbrktsbf'. Will it? the 'str()' and 'sub()' calls are undefined, so I don't think I can check the correctness really.
Liked the idea of the property of max(substr) - min(substr) + 1 == len(substr) though.
I think it should look something like this:
void substitute(char str[], char const * const pattern, char const * const replace_with) {
if(str == NULL || pattern == NULL || replace_with == NULL) {
cerr << "bad arguments" << endl;
exit(1);
}
char const *pattern_temp = pattern, *repl_with_temp = replace_with;
while(*pattern_temp && *repl_with_temp) {
++pattern_temp; ++repl_with_temp;
}
if(!*pattern_temp && *repl_with_temp) {
cerr << "pattern is smaller than replacement - insufficient memory space in string" << endl;
exit(1);
}
char *str_replace = str;
while(*str) {
char const *pat = pattern;
char const *repl_with = replace_with;
if(*str == *pat) {
// first symbol of pattern found in string
size_t count = 0;
while(*str && *pat && *str == *pat) {
++str; ++pat; ++count;
}
if(!*pat) {
// whole substring found
while(*repl_with) {
*str_replace++ = *repl_with++;
}
} else {
// otherwise, move symbols skipped when checking back to the string
while(count > 0) {
*(str_replace++) = *(str - (count--));
}
}
} else {
// if str_replace is already below str, then copy str to the new string
if(str_replace != str) {
*str_replace = *str;
}
++str_replace;
++str;
}
}
*str_replace = '\0';
}
I might be missing something, but I don't think the code will work for 'acb' string, it'll report the 'cb' part of it. No? Also s[left]!=s[right] - do we assume that all symbols are unique? or this should read while left != right?
Could you please add details to the code, so it's easier to understand? Thanks!
first multiply forward, so that b[i] contains the product of a[0]*a[1]*...*a[i-1]
b[0] = 1;
for(int j = 1; j < b.size(); ++j) {
b[j] = b[j - 1] * a[j - 1];
}
and then multiply backwards and multiply every b[i] by the product of all a[i+1]*...*a[n]
int back_mult = a[a.size() - 1];
for(int k = b.size() - 2; k >= 0; --k) {
b[k] = b[k] * back_mult;
back_mult *= a[k];
}
That's what I wanted to suggest as well, but the problem statement reads 'find the biggest BST', not the biggest BST size. Are we supposed to find the root node as well? Or really just the size?
- just_passing_through March 19, 2012In the O(n^2) approach aren't you counting the NULL'd left and right children of the leaf node as 2 nodes in the BST? I think the 'recursion stopping if' should read:
if(root->left == NULL && root->right == NULL) return 1;
No?
It's an infinite loop printing the same number that you fed the original call to MyFunction. Does not matter if the number is positive or negative. The postfix decrement returns the original n during evaluation, so you'll be stuck calling MyFunction(n) with the same value of n. And you'll never get to the second print due to the infinite loop, so the same number will be printed over and over and over again.
- just_passing_through March 29, 2012