Optimal Substructure: Interview Problem Survey

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.Wikipedia

In other words optimal solutions to sub-problems form the overall optimal solution.

Here we can use the property of optimal sub-structure to explore the space of all possible entries into a phone pad leetcode [17].

example instance;

"232"

example solution;

["ada","adb","adc","aea","aeb","aec","afa","afb","afc","bda","bdb","bdc","bea","beb","bec","bfa","bfb","bfc","cda","cdb","cdc","cea","ceb","cec","cfa","cfb","cfc"]

example code;

class Solver {
  unordered_map<char, string> operators = {
    {'2', "abc"}, {'3', "def"}, {'4', "ghi"},
    {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},
    {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
  }
  vector<string> SOLUTION;
  string packetNumber;

  //in order depth-first-search
  void depthFirstSearch(int index, string path) {
    if(path.length() == packet_number.length()) {
      solution.push_back(path);
      return
    }

    map<char, string>::iterator letters_iterator = operators.find(string[index]);
    for(char c : letters_iterator.second) {
      path.push_back(c);
      depthFirstSearch(index+1, path);
      path.pop_back();
    }
  }
public:
  vector<string> letterCombinations(string digits) {
    if(digits.length() == 0) {
      return SOLUTION;
    }
    packetNumber = digits;
    depthFirstSearch("", 0);
    return SOLUTION;
  }
}

Here the solution requires going through all possible state changes and should be seen as a graph where the number of nodes are 2^4*n where n is the number of digits in the input and we know and it's safe to assume n < "a relatively small constant" so we can bound or algorithm to be constant.

In this type of question we care about "revealing the search space" which should include a paper-napkin style verification the space is calculable.

next we can take a leetcode [743] which can be solved using Dijkstra's algorithm.

This is one of the properties in the ever famous Dijkstra's short path algorithm having optimal substructure we can take advantage of to not search the entire space of traversing the graph, the neat thing of Dijkstra's is we get to keep the structure to re-use.

Here the example being calculating Network Delay from one node to another.

class Solver {
private:
  struct comp { 
    bool operator()(const pair<int, int>& a, const pair<int, int> b) {
      return a.second > b.second;
    }
  }
public:
  networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int,int>>> graph(n+1);
    for(auto& t : times) {
      graph[t[0]].emplace_back(make_pair(t[1], t[2]));
    }

    vector<int> total_cost_to_travel(n+1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int,int>>, comp> pq;

    pq.push(make_pair(k, 0));
    total_cost_to_travel[k] = 0;

    int vertex_count = 0, maximum_delay = -1;
    while(not pq.empty()) {
      pair<int, int> edgeIn = pq.top(); pq.pop();
      if(total_cost_to_travel[edgeIn.first] < edgeIn.second) {
        continue;
      }
      ++vertex_count;
      maximum_delay = max(maximum_delay, total_cost_to_travel[edgeIn.first]);

      for(pair<int, int> edgeOut : graph[edgeIn.first]) {
        int edgeWeight = total_cost_to_travel[edgeOut.first];
        if(edgeWeight > edgeOut.second + edgeWeight) {
          total_cost_to_travel[edgeOut.first] = edgeOut.second + edgeWeight;
          pq.push(make_pair(edgeOut.first, tc[edgeOut.first]));
        }
      }
    } 
    return vertex_count == n ? maximum_delay : -1;
  }
}