Camelcase Matching in C++

Suppose we have a list of queries, and a pattern, we have to return an answer that will be list of booleans, where answer[i] is true if and only if queries[i] matches the pattern. A query word matches a given pattern when we can insert lowercase letters to the pattern word so that it equals the query.

So if the input is like ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"] and pattern = "FB", then the results will be [true,false,true,false,false].

To solve this, we will follow these steps −

• Define a method called insertNode(), this takes head and string s

• curr := head

• for i in range 0 to size of s – 1

  • x := s[i]

  • if child[x] of curr is not null, then child[x] of curr := new node

  • curr := child[x] of curr

• set isEnd of curr := true

• From the main method, do the following −

• head := new node, insert pattern into head, n := size of query array, m := size of temp, ok := true

• for j in range 0 to m – 1

  • x := temp[j]

  • if child[x] of curr, then curr := child[x] of curr

  • otherwise when temp[j] is in range A to Z, then ok := false and break from loop

  • ans[i] := isEnd of curr AND ok

• return ans

Example(C++)

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } struct Node{    bool isEnd;    map <char, Node*> child;    Node(){       isEnd = false;    } }; class Solution {    public:    void insertNode(Node* head, string s){       Node* curr = head;       for(int i = 0; i < s.size(); i++){          char x = s[i];          if(!curr->child[x]){             curr->child[x] = new Node();          }          curr = curr->child[x];       }       curr->isEnd = true;    }    vector<bool> camelMatch(vector<string>& queries, string pattern){       Node* head = new Node();       insertNode(head, pattern);       int n = queries.size();       vector <bool> ans(n);       Node* curr;       bool ok;       for(int i = 0; i < n; i++){          string temp = queries[i];          curr = head;          int m = temp.size();          ok = true;          for(int j = 0; j < m; j++){             char x = temp[j];             if(curr->child[x]){                curr = curr->child[x];             }             else if(temp[j] >= 'A' && temp[j] <= 'Z'){                ok = false;                break;             }          }          ans[i] = curr->isEnd && ok;       }       return ans;    } }; main(){    vector<string> v1 = {"FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"};    Solution ob;    print_vector(ob.camelMatch(v1, "FB")); }

Input

["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"] "FB"

Output

[1, 0, 1, 1, 0, ]