Image Uploading and Attaching for the Blog Project

Today I have been working on this feature that allows users to upload image as attachments and to include them as Markdown format.

Here’s a demo of the complete feature:

The first decision I made was how I should accept the upload. After several minutes of thinking with my pea brain, I decided to use multer to take file upload from clients. multer will put the file upload in a directory with a randomly generated name to avoid name duplications. It works well with express js in that it sets the ‘file’ property on req with useful properties such as filename, filesize and the path to the file.

Without much further thinking (which later proved to be a mistake), I thought it would be natural to simply serve the directory that has all the uploaded files.

So I wrote these:

API for upload

const express = require('express');
const router = new express.Router();
const fs = require('fs');
const multer = require('multer');
const upload = multer({ dest: 'uploads/' });
const auth = require('../auth');

const { ALLOWED_EXTENSIONS, MAX_SIZE } = require('../config');

router.post('/', [auth.admin, upload.single('upload')], (req, res, next) => {
  const filename = req.file.originalname;
  const path = req.file.path;

  const splitArr = filename.split('.');
  if (splitArr.length === 1 || !ALLOWED_EXTENSIONS.includes(splitArr.pop().toLowerCase())) {
    removeFile(path);
    return res.status(403).json({ message: 'Forbidden file extension' });
  }

  if (req.file.size > MAX_SIZE) {
    removeFile(path);
    return res.status(403).json({ message: `File exceeds maximum allowed size: ${MAX_SIZE / 1000000} MB` });
  }

  res.json({ path: req.file.path });
});

function removeFile(path) {
  fs.unlink(path, err => {
    if (err) console.log(err);
  });
}

module.exports = router;

serve directory:

app.use('/uploads', express.static('uploads'));

frontend’s upload method

onUpload() {
  if (!this.file) {
    this.props.displayMessage('You haven\'t selected any file yet!');
    return;
  }

  const data = new FormData();
  data.set('upload', this.file);
  instance.post('/uploads', data, {
    headers: { Authorization: 'Bearer ' + this.props.token },
  })
    .then(response => {
      const files = this.state.files.slice();
      files.push(response.data.path);
      this.setState({
        files,
      });
      console.log(files);
    })
    .catch(err => {
      this.props.displayMessage(err.response.data.message);
    });
}

This worked fine. However, when I deployed some other minor changes such as progress bar for upload and one click copy path button and hit refresh on my browser – the images were gone! I soon realized that it was because Docker created new containers because of the file changes, and the files on the original containers would be lost unless I do some backup or mount to the host.

That was when I decided to store all of the image files in MongoDB. In this way, the images are staying at the same place with the post contents, which makes backing up easy. It would also be easy to implement because I already had code for other schemas.

With some copy pasta

Schema for images:

const mongoose = require('mongoose');

const ImageShcema = new mongoose.Schema({
  data: Buffer,
  contentType: String,
}, { timestamps: true });

mongoose.model('Image', ImageShcema);

API handler for uploading and retrieving images:

const express = require('express');
const router = new express.Router();
const fs = require('fs');
const multer = require('multer');
const upload = multer({ dest: 'uploads/' });
const auth = require('../auth');
const mongoose = require('mongoose');
const Image = mongoose.model('Image');

const { ALLOWED_EXTENSIONS, MAX_SIZE } = require('../config');

router.get('/:id', (req, res, next) => {
  const id = req.params.id;
  Image.findById(id).exec()
    .then(image => {
      if (!image) {
        return res.sendStatus(404);
      }
      res.contentType(image.contentType);
      res.send(image.data);
    })
    .catch(err => {
      if (err.name === 'CastError') {
        return res.sendStatus(404);
      }
      next(err);
    });
});

router.post('/', [auth.admin, upload.single('upload')], (req, res, next) => {
  const filename = req.file.originalname;
  const path = req.file.path;

  const splitArr = filename.split('.');
  const extension = splitArr.pop().toLowerCase();
  if (!ALLOWED_EXTENSIONS.includes(extension)) {
    removeFile(path);
    return res.status(403).json({ message: 'Forbidden file extension' });
  }

  if (req.file.size > MAX_SIZE) {
    removeFile(path);
    return res.status(403).json({ message: `File exceeds maximum allowed size: ${MAX_SIZE / 1000000} MB` });
  }

  const image = new Image({
    data: fs.readFileSync(path),
    contentType: `image/${extension}`,
  });
  image.save()
    .then(saved => res.json({ path: `uploads/${saved._id}` }))
    .then(() => removeFile(path))
    .catch(next);
});

function removeFile(path) {
  fs.unlink(path, err => {
    if (err) console.log(err);
  });
}

module.exports = router;

I had to also catch ‘CastError’ in GET because the stupid mongoose throws when the param cannot be casted into ObjectId.

Basically what I do when the user uploads is storing the file to MongoDB, deleting the file in FS, and returning the ID of the file in the database. The ID can then be used for the GET api.

I’m also proud to say that this API endpoint is unit tested and (almost) fully covered. No I wish not to discuss the overall 0.2% coverage drop for the repo.

As I said above, I also added progress bar, feedback for copying path, error prompt for invalid files and some other UI features. The GitHub issue is now closed and I now just have to wait for the requester to come back online for my demo :).

Progress on blog rewrite

All right, this is where I say I can actually get something done.

Achievements for the blog project include:

  • APIs for log in/out, posts CRUD, comments CRUD, like/dislike
  • 93% coverage on APIs mentioned above
  • Using React-Redux to maximize data reuse and minimize the number of API calls
  • Using universal-cookie to store the logged in state (okay this might not deserve a stand alone bullet point)
  • Using Docker (Dockerfile and docker-compose) to automate the deployment process.

Today, lucky for you, I’ve decided to talk about how docker-compose in this project works.

Docker is the company driving the container movement and the only container platform provider to address every application across the hybrid cloud.

^ From Docker’s self introduction. What that means for me is that with proper usage, I wouldn’t have to set up production machines with all the dependencies that my project needs whenever I would like to deploy. Ideally all I would have to do is to write Dockerfiles and docker-compose.yml, install Docker and let Docker handle the rest.

In this blog project, separating the backend and the frontend, the dependencies (required on the environment, not the npm ones) are:

  • backend:
    • MongoDB
    • Node/npm
  • frontend:
    • Node/npm (for building)
    • Nginx (for serving)

With these in mind, I was able to write a Dockerfile and a docker-compose.yml for the backend following documentations and random StackOverflow answers online:

Dockerfile:

FROM node:carbon

WORKDIR /app

COPY package*.json ./

RUN npm install

COPY . .

RUN npm run build-server

EXPOSE 1717

RUN ["chmod", "+x", "/app/wait-for-it.sh"]

CMD ["node", "build/server.js"]

docker-compose.yml

version: '3'
services:
  blog-api:
    build:
      context: ./
      dockerfile: Dockerfile
    restart: always
    depends_on:
      - mongodb
    environment:
      MONGO_URL: mongodb://mongodb:27017/blog
    ports:
      - "1717:1717"
    command: bash /app/wait-for-it.sh mongodb:27017 -- node build/server.js
  mongodb:
    image: mongo:latest
    restart: always

The Dockerfile specifies the config for the blog-api container, while the docker-compose.yml tells Docker how my blog-api container relates to the mongodb service container.

Several things to notice:

  • Each Docker container is like a VM by itself, so the WORKDIR is the directory in the container, and when I do a ‘COPY . .’, naturally it copies from the current directory in the host to the current directory in the container.
  • Notice how I copied the package.json file first and npm installed before copying anything else. The reason for this is that Docker uses a layering cache system that is able to reuse previous versions of images if nothing changes in Dockerfile. Therfore if I only change some api route file, I wouldn’t have to wait for the long npm install process again.
  • wait-for-it is a tool to wait for a process to listen to a port before doing something. It has automatic retires that is very useful in this case. I could, however, just let blog-api restart always as is, but this tool doesn’t have as much overhead.

Later I added another Dockerfile for the frontend, which looks like this:

FROM nginx

RUN apt-get update

RUN apt-get install -y curl wget gnupg

RUN curl -sL https://deb.nodesource.com/setup_8.x | bash

RUN apt-get install -y nodejs

WORKDIR /app

COPY package*.json ./

RUN npm install

COPY . .

RUN npm run build

RUN cp -a /app/dist/* /usr/share/nginx/html

RUN cp /app/nginx.conf /etc/nginx/

This image extends from nginx, so the default CMD starts up the nginx server. I need nodejs for building the static files, so I added the couple lines there. The last two lines copy the static files to nginx’s serving directory and my config file to nginx’s config directory.

With the frontend added, I added one more service to docker-compose.yml:

web:
    build:
      context: ./
      dockerfile: Dockerfile-frontend
    restart: always
    ports:
      - "80:80"

This simply links my container for the web frontend to docker-compose so that I wouldn’t have to manually start up every container. Instead, I would only have to do docker-compose build and docker-compose up -d.

I also added automatic seeding for the MongoDB database but I’m too lazy to paste the steps here again so screw you.

This following point is unrelated to Docker, but I spent some time on it and felt like it would be interesting to include here. It is my nginx.conf file. Since I’m building the frontend with React single-page-serves-it-all pattern, I have to make sure that the nginx server returns the index.html file no matter what the sub url paths are. The only exception is that the client is requesting some js or resource file. With this in mind:

server {
    listen 80;
    root /usr/share/nginx/html;
    location / {
        try_files $uri /index.html;
    }
}

It tries to file the file specified in the uri first, before returning index.html regardless. 404 is handled on the frontend by my React application.

For the next step, I’ll be working on attachments to posts as a feature request from this person.

Rewrite(?) of this blog

I will be working on building a prettier blog (?) soon. The current tech stack selection is:

  • MongoDB
  • React
  • Express
  • Bootstrap
  • Travis
  • Docker
  • Mocha
  • Webpack

Tentative Feature List:

  • posts CRUD
  • users CRUD with admin
  • comments CRUD
  • posts like/share
  • categories and highlights of posts
  • hmmm I think that’s it, not too shabby

I’ll try to extract string literals specific for me in case some bored person on GitHub ever wants to reuse it (no).

Dumping this database and converting into MongoDB is going to be a PAIN IN THE ASS, so wish me luck LMAO.

If anyone’s reading this, hit me with some pretty frontend framework so I don’t have to freaking tweak the CSS and wanting to kill myself all the time.

Two blog posts in a day I’m on fire.

 

UPDATE ON April 28, 2018:

Repository is up here. Let’s see how much I can get done before my finals.

Automated iOS Testing with Appium and wd

Apparently someone checked out this blog during working hours and decided to tell me that I need to do an update.

Last month I was working on this mobile version of GitHub built with React-Native. The framework itself uses the same principle as React, which is component-oriented (is that a real word). However, I had most fun working on the automated testing on simulator and real device with Appium, the JSONWireProtocol implemented by wd, and Mocha.

Appium is a local server which accepts requests for UI testing. It supports languages including Java, Python and JavaScript with the same essential protocol. wd is one of the JavaScript libraries that implements the protocol AND has the most stars on GitHub, which is why I chose to use this one. Appium uses WebDriverAgent developed by Facebook to ‘control’ real devices and simulators. It also uses xcode dev tools to install apps and to inspect elements etc.

Appium has this concept called ‘desired capabilities’, which configures the testing environment. The capabilities I used for this UI test include:

  • udid, the unique identifier of the real device or simulator
  • platformName:’iOS’
  • platformVersion:’11.2′
  • app, the installation package of the app to be tested, .ipa for simulator, .app for device
  • xcodeOrgId, XCode devloper identifier
  • xcodeSigningId:’iPhone Developer’
  • deviceName, duh

here is the documentation for the desired capabilities. One important thing to note is that .ipa is the package extension for simulators and .app is the extension for devices. Methods to obtain them are documented in the README of my repository (link below).

With these in mind, I could start writing the tests. First and foremost, I needed to connect to Appium server with wd API like this:

const server = {
  host: 'localhost',
  port: 4723,
};
const driver = wd.promiseChainRemote(server);
const desired = {
  // desired capabilities above
};
driver.init(desired);

With the mapping provided on wd GitHub repo, I was then able to gradually implement my UI tests.

it('should display every tab', () => {
    return driver.waitForElementByName('Xuanyu Zhou', 6000)
      .then(el => {
        return driver.elementByName('Xuanyu Zhou').text();
      })
      .then(result => {
        result.should.be.equal('Xuanyu Zhou');
        return driver
          .elementByXPath('//XCUIElementTypeButton[contains(@name, "Public Repos")]')
          .click()
          .sleep(200)
      });
});

The above snippet is a mocha test that first waits for an element with name ‘Xuanyu Zhou’ to mount, then inspects the text ion that element. Afterwards, it uses XPath to select a button with name ‘Public Repos’, before it clicks on the button and sleeps for 200 milliseconds.

Apparently XPath’s documentation is hard to be found so it took me several StackOverflows to figure it out.

One neat thing about Appium-Desktop is that it has this inspector feature that lets you inspect the elements on the phone screen by clicking on them, just like Chrome’s developer tools. This is tremendously useful especially for the annoying XPaths.

Another interesting thing to note is that during testing I had this weird bug that although I had username and password inputs as different components, I could not click on them by themselves in the inspector. I also couldn’t select based on their names. It turned out I needed to make the input fields ‘accessible’ with React Native, documentation here. I guess Apple uses accessibility fields to give the elements names in testing. An Apple employee would be helpful here.

Repository

Testing Demo Episode 1:

Testing Demo Episode 2:

high efficiency vector using right value reference and std::move

#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
class Element {
private:
    int number;
public:
    Element() : number(0) {
        cout << "ctor" << endl;
    }
    Element(int num) : number(num) {
        cout << "ctor" << endl;
    }
    Element(const Element& e) : number(e.number) {
        cout << "copy ctor" << endl;
    }
    Element(Element&& e) : number(e.number) {
        cout << "right value ctor" << endl;
    }
    ~Element() {
        cout << "dtor" << endl;
    }
    void operator=(const Element& item) {
        number = item.number;
    }
    bool operator==(const Element& item) {
        return (number == item.number);
    }
    void operator()() {
        cout << number;
    }
    int GetNumber() {
        return number;
    }
};

template<typename T>
class Vector {
private:
    T* items;
    int count;
public:
    Vector() : count{ 0 }, items{ nullptr } {

    }
    Vector(const Vector& vector) : count{vector.count} {
        items = static_cast<T*>(malloc(sizeof(T) * count));
        memcpy(items, vector.items, sizeof(T) * count);
    }
    Vector(Vector&& vector) :count{ vector.count }, items{ vector.items } {
        vector.items = nullptr;
        vector.count = 0;
    }
    ~Vector() {
    }
    T& operator[](int index){
        if (index<0||index>=count) {
            cout<<"invalid index"<<endl;
            return items[0];
        }
        return items[index];
    }
    int returnCount(){
        return count;
    }
    void Clear() {
        for (int i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count = 0;
        items = nullptr;
    }

    void Add(const T& item) {
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count + 1)));
        int i;
        for (i = 0; i < count; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        new(&newItems[count])T(move(item));
        for (int i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count++;
        items = newItems;
    }
    bool Insert(const T& item,int index) {
        if (index < 0 || index >= count)
        {
            return false;
        }
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count + 1)));
        int i;
        for (i = 0; i < index; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        new(&newItems[index])T(move(item));
        for (i = index; i < count; i++)
        {
            new(&newItems[i+1])T(move(items[i]));
        }
        for (i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count++;
        items = newItems;
        return true;
    }
    bool Remove(int index) {
        if (index < 0 || index >= count)
        {
            return false;
        }
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count - 1)));
        int i;
        for (i = 0; i < index; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        for (i = index + 1; i < count; i++)
        {
            new(&newItems[i-1])T(move(items[i]));
        }
        for (i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count--;
        items = newItems;
        return true;
    }
    int Contains(const T& item) {
        for (int i = 0; i < count; i++)
        {
            if (items[i] == item)
            {
                return i;
            }
        }
        return -1;
    }
};

template<typename T>
void PrintVector(Vector<T>& v) {
    int count = v.returnCount();
    for (int i = 0; i < count; i++)
    {
        v[i]();
        cout << " ";
    }
    cout << endl;
}

int main() {
    Vector<Element> v;
    for (int i = 0; i < 4; i++) {
        Element e(i);
        v.Add(e);
    }
    PrintVector(v);
    Element e2(4);
    if (!v.Insert(e2, 10))
    {
        v.Insert(e2, 2);
    }
    PrintVector(v);
    if (!v.Remove(10))
    {
        v.Remove(2);
    }
    PrintVector(v);
    Element e3(1), e4(10);
    cout << v.Contains(e3) << endl;
    cout << v.Contains(e4) << endl;
    Vector<Element> v2(v);
    Vector<Element> v3(move(v2));
    PrintVector(v3);
    v2.Add(e3);
    PrintVector(v2);
    return 0;
}

output:

ctor
copy ctor
dtor
ctor
right value ctor
copy ctor
dtor
dtor
ctor
right value ctor
right value ctor
copy ctor
dtor
dtor
dtor
ctor
right value ctor
right value ctor
right value ctor
copy ctor
dtor
dtor
dtor
dtor
0 1 2 3 
ctor
right value ctor
right value ctor
copy ctor
right value ctor
right value ctor
dtor
dtor
dtor
dtor
0 1 4 2 3 
right value ctor
right value ctor
right value ctor
right value ctor
dtor
dtor
dtor
dtor
dtor
0 1 2 3 
ctor
ctor
1
-1
0 1 2 3 
copy ctor
1 
dtor
dtor
dtor

My Projects

I’ve decided to make a summary of my past projects here. I have spent most of my free time on iOS development, and also explored some web development using PHP and JavaScript. In the past summer I used JavaScript to work on an educational software for a CS professor here at Duke.

I’ve ordered them according to my personal preference:)

  1. DukeCSA

DukeCSA (on GitHub) is the iOS app started by Jay Wang (currently a senior at Duke) to fit the needs of Duke Chinese Student Association. I joined the team around Christmas 2015. It combined many useful functionalities:

  • events post – users can view upcoming and past events hosted by DukeCSA. They can sign up or comment on the events in the app.
  • Q&A – students can ask their peers about life at Duke. This section is like Quora for Duke.
  • Class Database – users can view a massive (1000+) collection of comments on courses offered here at Duke to help them make choices.
  • Crush – users can express their secret admiration to others. If there is a match, both users will get notifications.
  • Web event poster – a web interface for the CSA committee to post a new event. The event will then be saved to our database and all users will be notified. The user does not need to write any code.

short demos:
notification indication

web interface

Read more about iOS projects

 

2. JFLAP web

JFLAP (Java Formal Language and Automata Package) is an educational software about finite state machines, Moore and Mealy machines, Turing machines etc. I worked on building the online version of JFLAP and integrating JFLAP into OpenDSA (Data Structures and Algorithms) project.

The job included designing and implementing the user interface, optimizing and implementing the algorithms and migrating Java version to JavaScript. I learned about formal languages and automata as well as software development.

short demo:

more about JFLAPmore about OpenDSAdevelopment blog, web demo

 

3. 3D iOS games

I also learned about 3D iOS game development. Below are demo videos of them:

Marble Maze – gravity-controlled

Breakout

 

4. Tank Battle

This is a homework project in my software development class, but I treat it more than that. The game features elements such as stone, brick, grass and water. The player needs to protect the base and eliminate enemies. The game also uses permanent storage to present a leader board.

demo:


The design comes from the classic video game battle city.

 

5. Blog Post System

A blog post system written mainly with PHP. Responsive to both desktop and mobile devices. Users are able to view all posts without logging in and post articles or comments when logged in. Data is stored in MYSQL database. APIs are also built for possible iOS app development in the future.

demo: http://billyu.com (It’ll probably be more fun if you could read Chinese)

 

6. Wheeshare

(my first iOS app!). This is an iOS app that promotes sharing among Duke students. I completed this project with grant from Duke CoLab, my current employer.
On the platform, students are able to post their belongings to lend, or to browse through the available items and request to borrow with one click. Students can also easily manage their posts.

 

LeetCode 20. Valid Parentheses

Problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution:

public class Solution {
    public boolean isValid(String s) {        
        
        Stack<Character> stack = new Stack<>();
        
        for (int i =0; i<s.length(); i++){
            if (s.charAt(i) == ')' && (stack.isEmpty() || stack.pop() != '(')) return false;
            if (s.charAt(i) == '}' && (stack.isEmpty() || stack.pop() != '{')) return false;
            if (s.charAt(i) == ']' && (stack.isEmpty() || stack.pop() != '[')) return false;
            if (s.charAt(i) == '{' || s.charAt(i) == '(' || s.charAt(i) == '[') stack.push(s.charAt(i));
        }
        return stack.isEmpty();
    }
}

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Problem:

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int[] preorder, inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int n = preorder.length;
        return buildTree(0, n - 1, 0, n - 1);
    }
    
    private TreeNode buildTree(int pre1, int pre2, int in1, int in2) {
        if (pre2 < pre1) return null;
        if (pre2 == pre1) return new TreeNode(preorder[pre1]);
        TreeNode root = new TreeNode(preorder[pre1]);
        int pos = 0;
        for (int i = in1; i <= in2; i++) {
            if (inorder[i] == root.val) {
                pos = i;
                break;
            }
        }
        root.left = buildTree(pre1 + 1, pre1 + pos - in1, in1, pos - 1);
        root.right = buildTree(pre1 + pos - in1 + 1, pre2, pos + 1, in2);
        return root;
    }
}

LeetCode 150. Evaluate Reverse Polish Notation

Problem:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution:

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> nums = new Stack<>();
        Stack<String> ops = new Stack<>();
        for (String token: tokens) {
            if (isOp(token)) {
                if (nums.isEmpty()) {
                    ops.push(token);
                }
                else {
                    String num1 = nums.pop();
                    String num2 = nums.pop();
                    int a = Integer.parseInt(num1);
                    int b = Integer.parseInt(num2);
                    if (token.equals("+")) {
                        nums.push(a + b + "");
                    }
                    else if (token.equals("-")) {
                        nums.push(b - a + "");
                    }
                    else if (token.equals("*")) {
                        nums.push(b * a + "");
                    }
                    else {
                        nums.push(b / a + "");
                    }
                }
            }
            else {
                nums.push(token);
            }
        }
        String last = nums.pop();
        return Integer.parseInt(last);
    }
    
    private boolean isOp(String s) {
        String ops = "+-*/";
        return ops.indexOf(s) > -1;
    }
}

LeetCode 127. Word Ladder

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution:

Today I knew that building an adjacency map is a stupid, stupid solution when you have way more elements than path.

public class Solution {
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        wordList.add(endWord);
        Queue<String> current = new LinkedList<String>();
        int step = 1;
        current.offer(beginWord);
        while (!current.isEmpty()) {
            int size = current.size();
            while (size > 0) {
                String word = current.poll();
                if (word.equals(endWord))
                    return step;
                for (int i = 0; i < word.length(); i++) {
                    char[] arr = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        arr[i] = c;
                        String check = new String(arr);
                        if (!check.equals(word) && wordList.contains(check)) {
                            current.offer(check);
                            wordList.remove(check);
                        }
                    }
                }
                size--;
            }
            step++;
        }
        return 0;
    }
}