c++ - Determine running time of the code -


i have written following dp code today, worked fine got points in submission (here problem). not able determine running time of code. feel o(n^2 * log d) can't prove it.

class solution { public:     unordered_map<string, bool> m;     bool wordbreak(string s, unordered_set<string>& worddict) {         int n = s.length();         string t = "";         for(int i=0;i<n;i++){             t += s.at(i);             //cout << t << endl;             if(worddict.find(t) != worddict.end()){                 m[t] = true;                 string x = "";                 for(int j=i+1;j<n;j++){                     x += s.at(j);                 }                 if(x == ""){                     return true;                 }                 if(m.find(x) != m.end()){                     if(m[x] == true){                         return true;                     }else{                         continue;                     }                 }else{                     if(wordbreak(x, worddict)){                         m[x] = true;                         return true;                     }else{                         //cout << x << endl;                         m[x] = false;                         continue;                     }                 }             }else{                 //m[t] = false;             }         }         return false;     } };

it seems have o(n*n) complexity. use memorisation , every step of alrotithm produce @ least 1 new value in m. there n*n/2 substrings in string, find solution entire string n*n/2 passages in worst case.

ps: consider unordered_map works o(1).

edit:

it might more consider unordered_map works o(n) in case. m.find need calculate hash it's argument, wich string. may work faster if store indexes instead of string itself.


Comments

Post a Comment

Popular posts from this blog

1111. appearing after print sequence - php -

morning, i have code takes string of shoe sizes, explodes , puts in table. code works , info displayed correctly on page after table there few 1's after table. i'm confused this. so table looks (in columns of 3 on webpage) available in following sizes: 3 4 5 6 9 10 111 here's codes, purpose of example $x = 3|4|6|10|9 function get_sizes_pipe($x) { $counter = 0; $splits = explode("|",$x); asort($splits); $x = print "<table class='greentable'>"; $x .= print "<thead><tr><th scope='col' colspan='3' abbr='starter'>available in following sizes:</th></tr></thead><tbody><tr>"; foreach ($splits $split) { $entry = print "<td>".$split."</td>"; if($counter == 2){ $entry .= print "</tr><tr>"; $counter =0; } else { $counter++; ...
Read more

java - WARN : org.springframework.web.servlet.PageNotFound - No mapping found for HTTP request with URI [/board/] in DispatcherServlet with name 'appServlet' -

this question has answer here: why spring mvc respond 404 , report “no mapping found http request uri […] in dispatcherservlet”? 3 answers i trying making simple bbs i'm encountering following error, warn : org.springframework.web.servlet.pagenotfound - no mapping found http request uri [/board/] in dispatcherservlet name 'appservlet' i have tried solve error many times, have failed. how can solve error? here web.xml, controllerand , servlet-context. my web.xml <?xml version="1.0" encoding="utf-8"?> <web-app version="2.5" xmlns="http://java.sun.com/xml/ns/javaee" xmlns:xsi="http://www.w3.org/2001/xmlschema-instance" xsi:schemalocation="http://java.sun.com/xml/ns/javaee http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd"> <filter> <filter-nam...
Read more

node.js - Express and Redis - If session exists for this user, don't allow access -

i using redis , express this: // app.js var redis = require('redis'), redisclient = redis.createclient(), session = require('express-session'), redisstore = require('connect-redis')(session); session = session({ store: new redisstore({client: redisclient}), secret: 'secretkey', resave: true, saveuninitialized: true }) app.use(session); in index route file, set user session this: req.session.user = user; when user comes (or opens tab), how detect how many sessions having , block him access if has 1 active session? express-session working via cookies. had cookie named session sessionid. tabs inside browsed share cookies , can't rely on cookies if want strict working via 1 browser tab. you need create own sessions each opened browser tab. generating tabid @ client side , saving {userid, tabid} redis or can use websockets ( http://socket.io/ ) that, little overhead, doing want
Read more