abbreviation.cpp File Reference

Implementation of Abbrievation More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

Include dependency graph for abbreviation.cpp:

Go to the source code of this file.

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	abbreviation
	Functions for Abbreviation implementation.

Functions
bool	dynamic_programming::abbreviation::abbreviation_recursion (std::vector< std::vector< bool > > *memo, std::vector< std::vector< bool > > *visited, const std::string &str, const std::string &result, uint32_t str_idx=0, uint32_t result_idx=0)
	Recursive Dynamic Programming function.
bool	dynamic_programming::abbreviation::abbreviation (const std::string &str, const std::string &result)
	Iterative Dynamic Programming function.
static void	test ()
	Self test-implementations.
int	main ()
	Main function.

Detailed Description

Implementation of Abbrievation

Given two strings, a and b, determine if it's possible to make a equal to b You can perform the following operations on the string a:

1. Capitalize zero or more of a's lowercase letters.
2. Delete all of the remaining lowercase letters in a.

Algorithm

The idea is in the problem statement itself: iterate through characters of string a and b (for character indexes i and j respectively):

1. If a[i] and b[j] are equal, then move to next position
2. If a[i] is lowercase of b[j], then explore two possibilities: a. Capitalize a[i] or b. Skip a[i]
3. If the a[i] is not uppercase, just discard that character, else return false

Time Complexity: (O(|a|*|b|)) where |a| => length of string a

Author

Ashish Daulatabad

Definition in file abbreviation.cpp.

Function Documentation

abbreviation()

bool dynamic_programming::abbreviation::abbreviation	(	const std::string &	str,
		const std::string &	result )

Iterative Dynamic Programming function.

Returns whether s can be converted to t with following rules: a. Capitalize zero or more of s's lowercase letters from string s b. remove all other lowercase letters from string s Note: The transition states for iterative is similar to recursive as well

Parameters

str	given string, which might not be abbreivated
result	resultant abbreivated string

Returns

false if string str cannot be converted to result

true if string str can be converted to result

Definition at line 119 of file abbreviation.cpp.

                                                                 {
    std::vector<std::vector<bool>> memo(
        str.size() + 1, std::vector<bool>(result.size() + 1, false));
 
    for (uint32_t i = 0; i <= str.size(); ++i) {
        memo[i][0] = true;
    }
    for (uint32_t i = 1; i <= result.size(); ++i) {
        memo[0][i] = false;
    }
    for (uint32_t i = 1; i <= str.size(); ++i) {
        for (uint32_t j = 1; j <= result.size(); ++j) {
            if (str[i - 1] == result[j - 1]) {
                memo[i][j] = memo[i - 1][j - 1];
            } else if (str[i - 1] - 32 == result[j - 1]) {
                memo[i][j] = (memo[i - 1][j - 1] || memo[i - 1][j]);
            } else {
                if (str[i - 1] >= 'A' && str[i - 1] <= 'Z') {
                    memo[i][j] = false;
                } else {
                    memo[i][j] = memo[i - 1][j];
                }
            }
        }
    }
    return memo.back().back();
}

abbreviation_recursion()

bool dynamic_programming::abbreviation::abbreviation_recursion	(	std::vector< std::vector< bool > > *	memo,
		std::vector< std::vector< bool > > *	visited,
		const std::string &	str,
		const std::string &	result,
		uint32_t	str_idx = 0,
		uint32_t	result_idx = 0 )

Recursive Dynamic Programming function.

Returns whether s can be converted to t with following rules: a. Capitalize zero or more of a's lowercase letters from string s b. remove all other lowercase letters from string s

Parameters

memo	To store the result
visited	boolean to check if the result is already computed
str	given string, which might not be abbreivated
result	resultant abbreivated string
str_idx	index for string str, helpful for transitions
result_idx	index for string result, helpful for transitions

Returns

false if string str cannot be converted to result

true if string str can be converted to result

(str[i] == result[j]): if str char at position i is equal to result char at position j, then s character is a capitalized one, move on to next character str[i] - 32 == result[j]: if str[i] character is lowercase of result[j] then explore two possibilites:

1. convert it to capitalized letter and move both to next pointer (i + 1, j + 1)
2. Discard the character (str[i]) and move to next char (i + 1, j)

Definition at line 59 of file abbreviation.cpp.

                                                                           {
    bool ans = memo->at(str_idx).at(result_idx);
    if (str_idx == str.size() && result_idx == result.size()) {
        return true;
    } else if (str_idx == str.size() && result_idx != result.size()) {
        // result `t` is not converted, return false
        return false;
    } else if (!visited->at(str_idx).at(result_idx)) {
        if (str[str_idx] == result[result_idx]) {
            ans = abbreviation_recursion(memo, visited, str, result,
                                         str_idx + 1, result_idx + 1);
        } else if (str[str_idx] - 32 == result[result_idx]) {
            ans = abbreviation_recursion(memo, visited, str, result,
                                         str_idx + 1, result_idx + 1) ||
                  abbreviation_recursion(memo, visited, str, result,
                                         str_idx + 1, result_idx);
        } else {
            // if `str[i]` is uppercase, then cannot be converted, return
            // `false`
            // else `str[i]` is lowercase, only option is to discard this
            // character
            if (str[str_idx] >= 'A' && str[str_idx] <= 'Z') {
                ans = false;
            } else {
                ans = abbreviation_recursion(memo, visited, str, result,
                                             str_idx + 1, result_idx);
            }
        }
    }
    (*memo)[str_idx][result_idx] = ans;
    (*visited)[str_idx][result_idx] = true;
    return (*memo)[str_idx][result_idx];
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 192 of file abbreviation.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

test()

void test ( )

static

Self test-implementations.

Returns

void

Definition at line 153 of file abbreviation.cpp.

                   {
    std::string s = "daBcd", t = "ABC";
    std::vector<std::vector<bool>> memo(s.size() + 1,
                                        std::vector<bool>(t.size() + 1, false)),
        visited(s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    assert(dynamic_programming::abbreviation::abbreviation_recursion(
               &memo, &visited, s, t) == true);
    assert(dynamic_programming::abbreviation::abbreviation(s, t) == true);
    s = "XXVVnDEFYgYeMXzWINQYHAQKKOZEYgSRCzLZAmUYGUGILjMDET";
    t = "XXVVDEFYYMXWINQYHAQKKOZEYSRCLZAUYGUGILMDETQVWU";
    memo = std::vector<std::vector<bool>>(
        s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    visited = std::vector<std::vector<bool>>(
        s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    assert(dynamic_programming::abbreviation::abbreviation_recursion(
               &memo, &visited, s, t) == false);
    assert(dynamic_programming::abbreviation::abbreviation(s, t) == false);
 
    s = "DRFNLZZVHLPZWIupjwdmqafmgkg";
    t = "DRFNLZZVHLPZWI";
 
    memo = std::vector<std::vector<bool>>(
        s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    visited = std::vector<std::vector<bool>>(
        s.size() + 1, std::vector<bool>(t.size() + 1, false));
 
    assert(dynamic_programming::abbreviation::abbreviation_recursion(
               &memo, &visited, s, t) == true);
    assert(dynamic_programming::abbreviation::abbreviation(s, t) == true);
}