专栏首页cwl_Java经典算法题-矩阵中查找单词路径数

经典算法题-矩阵中查找单词路径数

1.问题描述

Problem Statement
问题陈述

You are given a String[] grid representing a rectangular grid of letters. You are also given a String find, a word you are to find within the grid. The starting point may be anywhere in the grid. The path may move up, down, left, right, or diagonally from one letter to the next, and may use letters in the grid more than once, but you may not stay on the same cell twice in a row (see example 6 for clarification).
你会得到一个字符串的数组,表示一个字符的矩阵,你还会得到一个字符串查找,需要在矩阵中查找这个单词,单词的开始点可能在矩阵的任意位置,方向可以是上,下,左,右,或者对角,也可能多次使用矩阵中的字符,但是你不可以在同一行的相同单元中两次。见例6

You are to return an int indicating the number of ways find can be found within the grid. If the result is more than 1,000,000,000, return -1.
你需要返回一个整数,表示在矩阵中发现的路径个数,如果返回的路径超过 1,000,000,000,就返回 -1。

Definition
定义

Class:
类名
WordPath

Method:
方法
countPaths

Parameters:
参数
String[], String

Returns:
返回值
int

Method signature:
方法签名
int countPaths(String[] grid, String find)

(be sure your method is public)一定要 public 


Constraints
约束条件
-
grid will contain between 1 and 50 elements, inclusive.
矩阵包含 1-50 个元素
-
Each element of grid will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
每一个元素包含 1-50 个大写字母 'A'-'Z'
-
Each element of grid will contain the same number of characters.
每一个元素包含相同数目的字符
-
find will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
查找的单词包含 1-50 个字符

Examples
举例
0)

{"ABC",
 "FED",
 "GHI"}
"ABCDEFGHI"
Returns: 1
返回 1
There is only one way to trace this path. Each letter is used exactly once.
只有一个路径可以查到

1)


{"ABC",
 "FED",
 "GAI"}
"ABCDEA"
Returns: 2
返回 2
Once we get to the 'E', we can choose one of two directions for the final 'A'.

2)


{"ABC",
 "DEF",
 "GHI"}
"ABCD"
Returns: 0
返回 0
We can trace a path for "ABC", but there's no way to complete a path to the letter 'D'.
3)


{"AA",
 "AA"}
"AAAA"
Returns: 108
返回 108

We can start from any of the four locations. From each location, we can then move in any of the three possible directions for our second letter, and again for the third and fourth letter. 4 * 3 * 3 * 3 = 108.
4)


{"ABABA",
 "BABAB",
 "ABABA",
 "BABAB",
 "ABABA"}
"ABABABBA"
Returns: 56448
返回 56448
There are a lot of ways to trace this path.
5)


{"AAAAA",
 "AAAAA",
 "AAAAA",
 "AAAAA",
 "AAAAA"}
"AAAAAAAAAAA"
Returns: -1
返回 -1

There are well over 1,000,000,000 paths that can be traced.
这个将超过 1,000,000,000 种路径,返回 -1
6)

????
{"AB",
 "CD"}
"AA"
Returns: 0
返回 0
Since we can't stay on the same cell, we can't trace the path at all.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

2.代码示例

public class WordPath {
	int m,n,count=0;
	char[] word;
	char[][] matrix;
	public int countPaths(String[] grid, String find) {
		m=grid.length;
		n=grid[0].length();
		matrix=new char[m][n];
		word=find.toCharArray();
		int i,j;
		for (i=0;i<m;i++) {
			for (j=0;j<n;j++) {
				matrix[i][j]=grid[i].charAt(j);
			}
		}
		for (i=0;i<m;i++) {
			for (j=0;j<n;j++) {
				if (matrix[i][j]==word[0]) {
					findNextChar(i,j,1);
				}
			}
		}
		if (count>1000000000)
			count=-1;
		return count;
	}
	boolean findNextChar(int x,int y,int c) {
		boolean found=false,findnext=false;
		if (x-1>=0&&x-1<m&&y-1>=0&&y-1<n) {
			if (matrix[x-1][y-1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x-1,y-1,c+1))
						findnext=true;
				}
			}
		}
		if (x-1>=0&&x-1<m&&y>=0&&y<n) {
			if (matrix[x-1][y]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x-1,y,c+1))
						findnext=true;
				}
			}
		}
		if (x-1>=0&&x-1<m&&y+1>=0&&y+1<n) {
			if (matrix[x-1][y+1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x-1,y+1,c+1))
						findnext=true;
				}
			}
		}
		if (x>=0&&x<m&&y-1>=0&&y-1<n) {
			if (matrix[x][y-1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x,y-1,c+1))
						findnext=true;
				}
			}
		}
		if (x>=0&&x<m&&y+1>=0&&y+1<n) {
			if (matrix[x][y+1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x,y+1,c+1))
						findnext=true;
				}
			}
		}
		if (x+1>=0&&x+1<m&&y-1>=0&&y-1<n) {
			if (matrix[x+1][y-1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x+1,y-1,c+1))
						findnext=true;
				}
			}	
		}
		if (x+1>=0&&x+1<m&&y>=0&&y<n) {
			if (matrix[x+1][y]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x+1,y,c+1))
						findnext=true;
				}
			}
		}
		if (x+1>=0&&x+1<m&&y+1>=0&&y+1<n) {
			if (matrix[x+1][y+1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x+1,y+1,c+1))
						findnext=true;
				}
			}
		}
		if (found&&findnext)
			return true;
		else return false;
	}
}
public class WordTest {
	public static boolean Test1() {
		WordPath wp=new WordPath();
		String[] grid={"ABC",
					   "FED",
					   "GHI"};
		String find="ABCDEFGHI";
		int key=1;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test2() {
		WordPath wp=new WordPath();
		String[] grid={"ABC",
					   "FED",
					   "GAI"};
		String find="ABCDEA";
		int key=2;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test3() {
		WordPath wp=new WordPath();
		String[] grid={"ABC",
					   "DEF",
					   "GHI"};
		String find="ABCD";
		int key=0;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test4() {
		WordPath wp=new WordPath();
		String[] grid={"AA",
                       "AA"};
		String find="AAAA";
		int key=108;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test5() {
		WordPath wp=new WordPath();
		String[] grid={"ABABA",
					   "BABAB",
					   "ABABA",
					   "BABAB",
					   "ABABA"};
		String find="ABABABBA";
		int key=56448;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test6() {
		WordPath wp=new WordPath();
		String[] grid={"AAAAA",
					   "AAAAA",
					   "AAAAA",
					   "AAAAA",
					   "AAAAA"};
		String find="AAAAAAAAAAA";
		int key=-1;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test7() {
		WordPath wp=new WordPath();
		String[] grid={"AB",
                       "CD"};
		String find="AA";
		int key=0;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static void main(String[] args) {
		if (Test1())
			System.out.println ("Test1 OK");
		if (Test2())
			System.out.println ("Test2 OK");
		if (Test3())
			System.out.println ("Test3 OK");
		if (Test4())
			System.out.println ("Test4 OK");
		if (Test5())
			System.out.println ("Test5 OK");
		if (Test6())
			System.out.println ("Test6 OK");
		if (Test7())
			System.out.println ("Test7 OK");
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java工具集-类(ClassUtils)

    cwl_java
  • 前端基础-JavaScript操作符

    cwl_java
  • 前端基础-JavaScript流程控制

    执行顺序:1243 ---- 243 -----243(直到循环条件变成false)

    cwl_java
  • 自己写个类加载器

    获取指定包下所有的类,需要将包名转换为文件路径,读class文件或者jar包,再去进行类加载:

    春哥大魔王
  • 蒂花之秀,他们究竟对古诗词做了什么?

    菜天哥哥
  • leetcode-125-Valid Palindrome

    Given a string, determine if it is a palindrome, considering only alphanumeric c...

    chenjx85
  • 1028 人口普查 (20 分)测试点3格式错误

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 全球34家金融科技独角兽:中国企业包揽前三甲,美国有18家入围!

    过去几年金融科技非常热门,天使投资者和风险投机构投入了数亿美元,甚至数十亿美元的资金。仅仅在2017年,根据毕马威的数据,金融科技企业就获得了惊人的310亿美元...

    点滴科技资讯
  • 使用Artik创建物联网项目

    Artik IoT平台是一个端到端的物联网平台,可协助我们构建出物联网项目。它是一个开放的平台,对多种不同设备提供云支持。通过Artik IoT,成功连接的设备...

    小芬达
  • C#网络编程(异步传输字符串) - Part.3

    这篇文章我们将前进一大步,使用异步的方式来对服务端编程,以使它成为一个真正意义上的服务器:可以为多个客户端的多次请求服务。但是开始之前,我们需要解决上一节中遗留...

    张子阳

扫码关注云+社区

领取腾讯云代金券