c++ 二维字符矩阵，字符串查找
这个项目一个区块链合作项目方发过来的水平测试题目，题目要求是：输入去掉空格，转换为大写字母，横向、纵向、对角线，以及相反方向去匹配，是否匹配到字符串。
题目内容：
按照如下示意图，在二维矩阵中查找字符串
设计方法有两种：
字符比较 字符串比较备注：第一版本时，我认为爬虫的方法不如字符串匹配的方法高效，因此我用了第二种方法。但是项目方回复的消息说60行也能搞定，因此处于工程师的荣耀，我写了第二版本的代码。
采用第一种方法时，参照爬虫设计思想
字符比较+递归version1
#include
#include
#include
#include
#include
using namespace std;
class Cmatrix {
public:
vector<vector> flag, array;
string key;
Cmatrix(vector<vector> & array_, string & key_) : array(array_), key(key_) {
flag.reserve(array.size());
for (int i=0; i<array.size(); i++) {
flag[i].reserve(array[i].size());
}
};
~Cmatrix() {}
bool exist(void) {
for(int i=0; i<array.size(); i++){
for(int j=0; j<array[0].size(); j++){
if(backtracking(0, i, j))
return true;
}
}
return false;
}
bool backtracking(int k, int i, int j) {
if(k == key.length())
return true;
if(i=array.size() || j=array[0].size() || flag[i][j]==1 || key[k]!=array[i][j])
return false;
flag[i][j] = 1;
if( backtracking(k+1, i+1, j) || backtracking(k+1, i-1, j) || backtracking(k+1, i, j+1) || backtracking(k+1, i, j-1) || backtracking(k+1, i+1, j-1) || backtracking(k+1, i+1, j+1) || backtracking(k+1, i-1, j-1) || backtracking(k+1, i-1, j+1) )
return true;
flag[i][j] = 0;
return false;
}
};
//g++ main.cpp -std=c++11
int main(int argc, char **argv)
{
if (argc < 2) {
cout << "usage:" << argv[0] << " input string" << endl;
return -1;
}
string key;
for (auto i = 1; i<argc; i++)
key += argv[i];
transform(key.begin(), key.end(), key.begin(), ::toupper);
vector<vector> matrix = { {'C', 'O', 'A', 'S', 'T'},
{'X', 'O', 'L', 'O', 'E'},
{'E', 'M', 'A', 'I', 'A'},
{'L', 'S', 'O', 'T', 'M'},
{'T', 'N', 'A', 'X', 'O'}};
Cmatrix mat(matrix, key);
cout << (mat.exist() == true ? "Found" : "Not Found") << endl;
return 0;
}
采用的第二种方法时，字符串比较是一个调用，那么任务就具体到了各个方向字符串的生成：
横向、纵向、对角线皆可生成字符串。
字符串比较version2
#include
#include
#include
using namespace std;
bool find_(string & str, string & key)
{
// 正向字符串匹配
if (str.find(key) != string::npos) {
return true;
}
// 反向字符串匹配
reverse(str.begin(), str.end());
if (str.rfind(key) != string::npos) {
return true;
}
return false;
}
/*
compiler command in linux: g++ -std=c++11 search.cpp -o search
*/
int main(int argc, char **argv)
{
const int ROWS = 5;
const int COLUMNS = 5;
char matrix[ROWS][COLUMNS] = { {'C', 'O', 'A', 'S', 'T'},
{'X', 'O', 'L', 'O', 'E'},
{'E', 'M', 'A', 'I', 'A'},
{'L', 'S', 'O', 'T', 'M'},
{'T', 'N', 'A', 'X', 'O'}};
#if 0
string str;
getline(cin,str);
cout << str << endl;
#endif
//cout << "argc=" << argc << endl;
if (argc < 2) {
cout << "usage:" << argv[0] << " input string" << endl;
}
// 从cli获取目标字符串，并转换为大写
string key;
for (auto i = 1; i<argc; i++) {
key += argv[i];
}
transform(key.begin(), key.end(), key.begin(), ::toupper);
//cout << "key:" << key < ROWS || key.length() > COLUMNS) {
cout << "your key more than max " < COLUMNS ? ROWS : COLUMNS) << " bytes" << endl;
}
// 横向检测
for (auto i=0; i<ROWS; i++) {
string str(&matrix[i][0], COLUMNS);
//cout << str << endl;
if (find_(str, key)) {
cout << "Found" << endl;
return 0;
}
}
// 纵向检测
for (auto i=0; i<COLUMNS; i++) {
string str;
for (auto j=0; j<ROWS; j++) {
str += matrix[j][i];
}
//cout << str << endl;
if (find_(str, key)) {
cout << "Found" << endl;
return 0;
}
}
// 沿主对角线方向，从右上角打印到左下角
int x, y;
x = 0;
y = ROWS - 1;
while (x != ROWS) {
string str;
for (int i = x, j = y; i <= ROWS - 1 && j <= ROWS - 1; i++, j++) {
str += matrix[i][j];
}
if (find_(str, key)) {
cout << "Found" < 0) {
y--;
}
else {
x++;
}
}
// 沿副对角线方向，从左上角打印到右下角
x = 0;
y = 0;
while (x < ROWS) {
string str;
for (int i = x, j = y; i = 0; i++, j--) {
str += matrix[i][j];
}
if (find_(str, key)) {
cout << "Found" << endl;
return 0;
}
if (y < ROWS - 1) {
y++;// 先往右走
}
else {
x++;// 往右走不动了再往下走
}
}
cout << "Not found" << endl;
return 0;
}
执行效果：
[root@izwz93atpalb56zydy9bpyz case1]# ./search XOL
Found
[root@izwz93atpalb56zydy9bpyz case1]# ./search OLox
Found
[root@izwz93atpalb56zydy9bpyz case1]# ./search XMOX
Found
[root@izwz93atpalb56zydy9bpyz case1]# ./search OTA
Found
[root@izwz93atpalb56zydy9bpyz case1]# ./search OTAO
Found
[root@izwz93atpalb56zydy9bpyz case1]# ./search Eio
Found
[root@izwz93atpalb56zydy9bpyz case1]# ./search tsao
Found
[root@izwz93atpalb56zydy9bpyz case1]# ./search oast
Found
[root@izwz93atpalb56zydy9bpyz case1]#
查看专栏详情
立即解锁全部专栏
作者：唐一墨
