LeetCode 780. Reaching Points - Weekly Contest 71

https://leetcode.com/contest/weekly-contest-71/problems/reaching-points/

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

	class Solution {
	public boolean reachingPoints(int sx, int sy, int tx, int ty) {
	// filter abnormal cases
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	if (Math.min(sx, sy) > Math.min(tx, ty)) {
	System.out.println(1);
	return reachingPoints1(sx, sy, tx, ty);
	} else {
	System.out.println(2);
	return reachingPoints2(sx, sy, tx, ty);
	}
	}
	private int sx;
	private int sy;
	HashSet<Entry> isVisited2 = new HashSet<>();
	public boolean reachingPoints2(int sx, int sy, int tx, int ty) {
	// filter abnormal cases
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	isVisited2.clear();
	this.sx = sx;
	this.sy = sy;
	return helper2(tx, ty);
	}
	public boolean helper2(int tx, int ty) {
	if (isVisited2.contains(new Entry(tx, ty))) {
	return false;
	}
	if (this.sx == tx && this.sy == ty) {
	return true;
	}
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	isVisited2.add(new Entry(tx, ty));
	return helper2(tx - ty, ty) || helper2(tx, ty - tx);
	}
	private int tx;
	private int ty;
	HashSet<Entry> isVisited = new HashSet<>();
	public boolean reachingPoints1(int sx, int sy, int tx, int ty) {
	// filter abnormal cases
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	isVisited.clear();
	this.tx = tx;
	this.ty = ty;
	return helper(sx, sy);
	}
	public boolean helper(int sx, int sy) {
	if (isVisited.contains(new Entry(sx, sy))) {
	return false;
	}
	if (sx == this.tx && sy == this.ty) {
	return true;
	}
	if (sx > tx || sy > ty) {
	return false;
	}
	if (sx == tx) {
	return (ty - sy) % sx == 0;
	}
	if (sy == ty) {
	return (tx - sx) % sy == 0;
	}
	isVisited.add(new Entry(sx, sy));
	return helper(sx + sy, sy) || helper(sx, sx + sy);
	}
	class Entry {
	int x;
	int y;
	public Entry(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}
	}

view raw LC 780. Reaching Points - Weekly Contest 71 - LeetCode.java hosted with ❤ by GitHub